Heap Array not working

Question

I am writing a program to build a heap array from a usual array and it just doesn't work. We have to use this sudo code which I used to write my rebuildHeap function but I don't know what I am doing wrong. Could someone spot any mistakes?

rebuildHeap is used after the replacement node has taken the place of root

rebuildHeap(heap, index, lastIndex)
1 if (index * 2 + 1 <= lastIndex)
  1 leftKey = heap[index*2+1].key
  2 if (index * 2 + 2 > lastIndex)
    1 largeChildIndex = index * 2 + 1
  3 else 
    1 rightKey = heap[index*2+2].key
    2 if (leftKey > rightKey)
          1 largeChildIndex = index * 2 + 1
    3 else
          1 largeChildIndex = index * 2 + 2
   4 end if
  4 end if
  5 if (heap[index].key < heap[largeChildIndex].key)
   1 swap (heap[index], heap[largeChildIndex])
   2 rebuildHeap(heap, largeChildIndex, lastIndex)
  6 end if
2 end if

and this is my code.. so first I create an array of int and store some random values then I run create heap function which calls rebuildHeap till heap array is complete.

EDITED, removed the array size..

void rebuildHeap(int heap[], int index, int lastindex) {
int leftkey = 0 ;
int largeChildIndex = 0;
int rightkey = 0;
cout << endl;

if (heap[index*2+1] <= heap[lastindex])
{
    leftkey = heap[index*2+1];
    cout <<" index : "  << index*2+1 << " leftkey  " << leftkey << endl;
    cout <<" index : "  << lastindex << " heap[lastindex] = " << heap[lastindex] <<       endl;


    if ((heap[index * 2+ 2]) > heap[lastindex])
        largeChildIndex = (index* 2) +1;

    else
    {
        rightkey = heap[index*2+2];

        if (leftkey > rightkey)
            largeChildIndex = index * 2  +1;
        else
            largeChildIndex = index*2+2;
    }
}

if (heap[index] < heap[largeChildIndex]) {
    swap(heap[index], heap[largeChildIndex]);
    rebuildHeap(heap, largeChildIndex, lastindex);
}
}


void swap (int &a, int &b) {
int temp = b;
b = a;
a = temp;
}


int main(int argc, const char * argv[])
{

int a[]  = {3, 7, 12, 15, 18, 23, 4, 9, 11, 14, 19, 21};

int length = (sizeof(a)/sizeof(a[0]));
for (int i = length/2-1; i >= 0; i-- ) {
    rebuildHeap(a, i, length-1);
    cout << " i " << i;
}

for (int i = 0; i < length; i++) {
    cout << endl<< a[i] << endl;
}

 };

Answer 1

First of all I would like to highlight that your translation of the pseudocode was wrong, so I fixed it.

#include <iostream>

using namespace std;

void rebuildHeap(int *heap, int index, int lastindex)
{
    int leftkey = 0 ;
    int largeChildIndex = 0;
    int rightkey = 0;

    if ((index*2 + 1) <= lastindex)
    {
        leftkey = heap[index*2+1];

        if ((index*2 + 2) > lastindex)
            largeChildIndex = index*2 +1;

        else
        {
            rightkey = heap[index*2+2];

            if (leftkey > rightkey)
                largeChildIndex = index*2+1;
            else
                largeChildIndex = index*2+2;
        }
    }
    else
    {
        return;
    }
    if (heap[index] < heap[largeChildIndex]) {
        swap(heap[index], heap[largeChildIndex]);
        rebuildHeap(heap, largeChildIndex, lastindex);
    }

}


void swap (int &a, int &b) {
int temp = b;
b = a;
a = temp;
}


int main(int argc, const char * argv[])
 {

int a[]  = {3, 7, 12, 15, 18, 23, 4, 9, 11, 14, 19, 21};

int length = sizeof(a)/sizeof(a[0]);

//create heap
for (int i = (length/2-1); i >= 0; i --)
{
    rebuildHeap(a, i, length-1);
}

//prints the heap array
for (int i = 0; i < length; i++) {
    cout << a[i] << " ";
}

return 0;
}

Here is the output: 23 19 21 15 18 12 4 9 11 14 7 3

My understanding of heap is like 0 so I'm not sure what is your expected output.