heap sort C - improper output

Question

I'm trying to implement heap sort for an array of 10 elements in ascending order. I'm following these steps -

heap_sort(arr,size_array):

 build_max_heap(arr)
    for(parent=size_array to 1):
       swap(arr[1],arr[parent])
       size_array = size_array - 1;
       max_heapify(arr,1,size);

But my output is totally messed up. I can't figure out where I'm going wrong.

This is my input -

20  15  10  1   15  9   2   6   7   9

My build_max_heap output -

20  15  10  7   15  9   2   6   1   9

My sorted array is the same as the build_max_heap output -

20  15  10  7   15  9   2   6   1   9

What am I doing wrong?

Here's my code:

    void max_heapify(int *arr,int i,int size)
{
    //i is the index of parent node. 2i is left child, 2i+1 is right
    int left = (2*i)+1;
    int right = (2*i)+2;
    int max;
    int temp;

    //check which node is the max, parent or one of its children. store max idx.
    if ((left<=size)&&(arr[left]>arr[i]))
        max = left;
    else
        max = i;
    if ((right<=size)&&(arr[right]>arr[max]))
        max = right;

    //swap parent with max.
    if(max!=i)
    {
        temp = arr[max];
        arr[max]=arr[i];
        arr[i]=temp;
        max_heapify(arr,max,size);
    }

}

void build_max_heap(int *arr,int size)
{
    for(int i = size/2; i>=0; i--)
    {
        max_heapify(arr,i,size);
    }
}

void heap_sort(int *arr, int size)
{
    int temp;
    build_max_heap(arr,size);
    int i = size;
    while(size>0)
    {
        //swap
        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //reduce size
        size = size -1;
        //heapify
        max_heapify(arr,0,size);

    }
}

Answer 1

Your code accesses the element arr[size] several times, which is one item beyond the valid range, 0 <= index < size. In particular:

if ((left<=size)&&(arr[left]>arr[i]))
    max = left;
else
    max = i;
if ((right<=size)&&(arr[right]>arr[max]))
    max = right;

Here, you should replace all ... <= size with ... < size.

int temp;
build_max_heap(arr,size);
int i = size;
while(size>0)
{
    //swap
    temp = arr[i];
    arr[i] = arr[0];
    arr[0] = temp;
    //reduce size
    size = size -1;
    //heapify
    max_heapify(arr,0,size);

}

Here, you use two variables, i and size, but you update only size. The index i will always be out of range, because i < size is never true. You should use and alter only one variable through the loop.

You can omit i altogether, but note how you'll always access the item one place beyond the array. Therefore, you should decrease size before you swap the elements.

(You can contract while (size > 0) { size = size - 1; ...} to while (size--) .... That's a useful idiom for iterating backwards: Backwards iterations decreease the index before the loop body; forward iterations increase the index after the loop body.)

Putting it all together:

void max_heapify(int *arr, int i, int size)
{
    //i is the index of parent node. 2i is left child, 2i+1 is right
    int left = 2*i + 1;
    int right = 2*i + 2;
    int max;

    if (left < size && arr[left] > arr[i])
        max = left;
    else
        max = i;

    if (right < size && arr[right] > arr[max])
        max = right;

    if (max != i) {
        int temp = arr[max];
        arr[max]=arr[i];
        arr[i]=temp;

        max_heapify(arr,max,size);
    }

}

void build_max_heap(int *arr,int size)
{
    int i = size / 2; 

    while (i--) {
        max_heapify(arr, i, size);
    }
}

void heap_sort(int *arr, int size)
{
    build_max_heap(arr, size);

    while (size--) {
        int temp = arr[size];
        arr[size] = arr[0];
        arr[0] = temp;

        max_heapify(arr, 0, size);
    }
}