This is a question related to C language Heap.

typedef struct HeapElement
{
    DSKEY  heKey;
    void *  heData;
} } HeapElement;

struct Heap
{
    int         hpMode; /* Minimize or Maximize */
    int         hpSize;
    int        hpFilled;
    int        hpGrowBy;
    HeapElement**  hpArray;
    HEAPCMPFUNC    hpCmpFunc;
    HEAPCHGFUNC    hpChgFunc;   // *(void*, jnt)
};

heapInsert(HEAP heap,const DSKEY key,void *data)
{
    Heap    *   h = (Heap*)heap;
    HeapElement *   he;
    int         i, pidx;
    HeapInternCmp   cmp_func;

    //Maxhip, Minhip setting
    if (h->hpMode == HEAP_MINIMIZE)
        cmp_func = heap_larger;
    else 
        cmp_func = heap_smaller;

    /* /* 1. Make a new element */
    he = heap_new_element(key,data);

    /* /* 2. Grow the heap if needed */

    if (NEEDS2GROW(h) && heap_grow(h))

    /* /* 3. Insert the new element into the heap */

    i = HSIZE(h);
    pidx = HPARENT(i);
    printf("i: %d pidx: %d\n",  i, pidx);
    int pdd;
    int hed;
    if(pidx >= 0)
    {
        pdd = *(int*)HARRAY(h, pidx)->heKey;
        hed = *(int*)he->heKey;

        printf("pidx: %d, he: %d\n", pdd, hed);
    }

    while (i > 0 && cmp_func(h,HARRAY(h,pidx),he))
    {
        int t = pidx;
        HARRAY(h, pidx) = HARRAY(h, i);
        HARRAY(h,i) = HARRAY(h, t) ;

        i = pidx;
        pidx = HPARENT(i);
    }

console

I would like to ask you a question among the Heap The code is ADT, which inserts new keys and data into the heap. Run it repeatedly in the main. (Handle it as the same as KEY and DATA.) The question I want to ask is, as you can see on the console screen, I've definitely saved the first input value of 14 in heap 0, but somehow in the next call, the value of 0 is not 14, and then the input is 25... I guess it's a reference question, but I don't know how to fix it.ㅠ<

c c++ heap pointer

2022-09-22 14:41

2 Answers

For max heap, the normal behavior is that the top element is changed to 25 when entered in the order of 14 -> 25.

Before you move to the code, it is very helpful to draw with your hands how the data is entered and deleted in the tree.

Hip tree action

2022-09-22 14:41

Swap is invalid at the end of HeapInsesrt.

    while (i > 0 && cmp_func(h,HARRAY(h,pidx),he))
    {
        int = pidx; // t and pidx are the same, so there is no space for temporary storage.
        HARRAY(h, pidx) = HARRAY(h, i);
        HARRAY(h,i) = HARRAY(h, t) ;

        i = pidx;
        pidx = HPARENT(i);
    }

I think it should be modified similar to the following.

    while (i > 0 && cmp_func(h,HARRAY(h,pidx),he))
    {
        HeapElement; // If HARRAY returns HeapElement..
        // Or, if you have an empty space in Heap, you can use that space.
        t = HARRAY(h, pidx);
        HARRAY(h, pidx) = HARRAY(h, i);
        HARRAY(h,i) = t

        i = pidx;
        pidx = HPARENT(i);
    }

2022-09-22 14:41

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656