Search code examples
data-structuresansi-c

Why are my MaxHeapify and BuildMaxHeap procedures failing to organise a heap?


In my ansi-c implementation of heap I have two procedures:

void MaxHeapify(Heap * h, int i)
{
    int l = Left(i);
    int r = Right(i);
    int L, tmp;

    if(l < h->heapsize && h->data[l] > h->data[i]) L = l;
    else L = i;

    if(r < h->heapsize && h->data[r] > h->data[L]) L = r;
    if(L != i)
    {
        tmp = h->data[i];
        h->data[i] = h->data[L];
        h->data[L] = tmp;
        MaxHeapify(h, L);
    }
}

void BuildMaxHeap(Heap * h)
{
    int i;
    h->heapsize = h->length;
    for(i = h->length / 2; i >= 0; i--)
    MaxHeapify(h, i);
}

And main.c

int main(int argc, char *argv[])
{
    int i;
    Heap h;
    int tab[] = {4,1,3,2,16,9,10,14,8,7};
    HeapInit(&h, tab, 10);
    for(i = 0; i < 10; i++) printf("%d ", h.data[i]);
    printf("\n");
    BuildMaxHeap(&h);
    for(i = 0; i < 10; i++) printf("%d ", h.data[i]);

    return 0;
}

I have strange output: 16 14 10 10 8 1 4 2 3 7 I've checked code a few times, but found nothing wrong.

CORRECTED NODE INDEX RETURNING FUNCTIONS:

int Left(int i)
{
    return 2*i+1;
}
int Right(int i)
{
    return 2*i+2;
}

Solution

  • @JimMischel posted correct answer in comments. It was written basing on pseudocode with indexing from 1 and that confused me. Correct code posted (via edit) in question.