Why is my HeapSort skipping the first element in the array?

Question

Im implementing HeapSort for an assignment in my algorithms class, and Im finally done, but for some reason, the sort is skipping over the first element in my array.

Original array:

int heapArray[SIZE] = {  5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55 };

Output after HeapSort()

5 99 32 15 13 12 8 4 1

Iv gone through all the functions and cant figure out why its skipping the first element. Can anyone help me out? Iv included all the HeapSort functions below. I know its alot to look at, but im sooooo close.

int main()
{
int heapArray[SIZE] = {  5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55 };
HeapSort(heapArray);


return 0;

}

.........................................................................................

void HeapSort(int heapArray[])
{   
int heap_size = SIZE;
int n = SIZE;
int temp;

Build_Max_Heap(heapArray);

for(int i = n-1; i >= 2; i--)
{
    temp = heapArray[1];
    heapArray[1] = heapArray[i];
    heapArray[i] = temp;

    heap_size = heap_size-1;
    Max_Heapify(heapArray,1);
}

return;
}

...........................................................................................

void Build_Max_Heap(int heapArray[])
{
double n = SIZE;

for(double i = floor((n-1)/2); i >= 1; i--)
{
    Max_Heapify(heapArray,i);
}

return;
}

...........................................................................................

void Max_Heapify(int heapArray[],int i)
{
int n = SIZE;
int largest = 0;
int l = Left(i);
int r = Right(i);

if(( l <= n) && (heapArray[l] > heapArray[i]))
{
    largest = l;
}
else
{
    largest = i;
}

if( (r <= n) && ( heapArray[r] > heapArray[largest]))
{
    largest = r;
}

int temp;
if(largest != i)
{
    temp = heapArray[i];
    heapArray[i] = heapArray[largest];
    heapArray[largest] = temp;

    Max_Heapify(heapArray,largest);
}

return;
}

...........................................................................................

int Parent(int i)
{
return (i/2);
}

int Left(int i)
{
return (2*i);
}

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

Answer 1

You have several issues in your code:

Firstly: array indices start from 0 not 1, therefore, there are many places with index errors listed as follows:

In HeapSort function:

for(int i = n-1; i >= 2; i--)  {
                   //should be 1 not 2
    temp = heapArray[1]; //should be 0 not 1 in those 2 statements
    heapArray[1] = heapArray[i];
     heapArray[i] = temp;  
}

Max_Heapify(heapArray,1);
                  //should start from 0 not 1

Besides:

for(double i = floor((n-1)/2); i >= 1; i--)
{                             //should start from 0 not 1
    Max_Heapify(heapArray,i);
}

You Parent, Left and Right have similar errors, you can see the above two posts.

Meanwhile, You have logical errors in you HeapSort and Max_Heapfiy function. You define heap_size and update it, but you never really used it. You have to pass it into the Max_Heapify function. Since each time when you put the current largest element to the end of the array, you only need to heapify the remaining elements not the whole heap anymore. This also means that your heapify function has errors since you never really used heap_size. The correct HeapSort and Max_Heapify as well as Build_Max_Heap function should be:

HeapSort:

void HeapSort(int heapArray[]) 
{   
  //do what you did before this sentence
  Build_Max_Heap(heapArray,heap_size); 
  //need to pass heap_size since Max_Heapify use heap_size
  for(int i = n-1; i >= 1; i--)
  {
     //...same as you did but pay attention to index
     heap_size = heap_size-1;
     Max_Heapify(heapArray,0,heap_size); //remember to use heap_size
   }
   //you declared void, no need to return anything
 }

Build_Max_Heap function:

void Build_Max_Heap(int heapArray[], int heapSize) //should use heapSize
{
    int n = SIZE;
    for(int i = floor((n-1)/2); i >= 0; i--) //here should be 0 not 1
   {
      Max_Heapify(heapArray,i,heapSize); //should use heapSize
    }
 }

Max_Heapify function:

void Max_Heapify(int heapArray[],int i, int heap_size) //should use heap_size
{
    //....here similar to what you did
    if(( l < heap_size) && (heapArray[l] > heapArray[i]))
    {   //^^compare with heap_size not SIZE
        //skip identical part
    }

    if( (r < heaps_ize) && ( heapArray[r] > heapArray[largest]))
    {
       //same error as above
    }

   //skip identical part again
   Max_Heapify(heapArray,largest, heap_size); //have to use heap_size
 }
}

You may need to get a better understanding of the HeapSort algorithm from the pseudocode.

Answer 2

here

Build_Max_Heap(heapArray);

for(int i = n-1; i >= 2; i--)
{                 ^^^^^
    temp = heapArray[1];
    heapArray[1] = heapArray[i];
    heapArray[i] = temp;

    heap_size = heap_size-1;
    Max_Heapify(heapArray,1);
}

return;
}

you stop looping on i=2, decrease it to 1, don't take first element of heapArray which is indexed by 0

Answer 3

The Parent, Left and Right functions are fit for 1-based arrays. For 0-based you need to use:

int Parent(int i)
{
    return (i - 1) / 2;
}

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

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

As you can check on example heap:

    0
   / \
  1   2
 / \ / \
3  4 5  6