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;
}
@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.