What is wrong with my Heapsort?

Question

For some reason my Heapsort is not working correctly. Using the following test program:

int main()
{
    AddArrayElement(10);
    AddArrayElement(110);
    AddArrayElement(20);
    AddArrayElement(100);
    AddArrayElement(30);
    AddArrayElement(90);
    AddArrayElement(40);
    AddArrayElement(80);
    AddArrayElement(50);
    AddArrayElement(70);
    AddArrayElement(60);

    HeapSort();
    PrintHeap();

    system("pause");
    return 0;
}

I get the following output:

Heap has Elements...110, 100, 80, 70, 90, 40, 10, 50, 30, 60, 20,

You see, the array is not being sorted.

It was expecting the result to be sorted like 10, 20, 30, ...., 110,

I verified the following:

• ShiftDown() is working correctly.
• Heapify() is working correctly.

But the HeapSort() function is not being able to sort the array.

Can anyone please help me to find the bug? Is it in my logic or anything else?

#include "Heap.h"
#include <stdio.h>  
#include <math.h>

int array[SIZE] = {0};
int lastElementIndex = -1;

void PrintHeap()
{
    int i=0;

    printf("\n\n");

    if(lastElementIndex >= 0)
    {
        printf("Heap has Elements...");

        for(i=0 ; i<=lastElementIndex ; i++)
        {
            printf("%d, ", array[i]);
        }
    }
    else
    {
        printf("Heap is Empty...");
    }

    printf("\n\n");
}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void SwapElements(int i, int j)
{
    Swap(&array[i], &array[j]);
}

void SetRootElement(int element)
{
    array[0] = element;
}

void DeleteRightMostElement()
{
    array[lastElementIndex] = EMPTY;

    --lastElementIndex;
}

void AddArrayElement(int element)
{
    ++lastElementIndex;

    array[lastElementIndex] = element;
}

#pragma region HasXXX()
int HasAnyElement()
{
    if(lastElementIndex > -1) return 1;
    else return 0;
}

int HasLeftChild(int i)
{
    int lastIndex = EMPTY;

    if(HasAnyElement())
    {
        lastIndex = GetLastElementIndex();

        if(lastIndex<=0 || lastIndex==i)
        {           
            return 0;
        }
        else
        {
            if(2*i+1 <= GetLastElementIndex()) return 1;
            else return 0;
        }
    }
    else
    {
        return 0;
    }
}

int HasRightChild(int i)
{
    int leftChildIndex = EMPTY;
    int rightChildIndex = EMPTY;

    if(HasAnyElement())
    {
        if(HasLeftChild(i))
        {           
            leftChildIndex = GetLeftChildIndex(i);
            rightChildIndex = leftChildIndex + 1;

            if(rightChildIndex <= GetLastElementIndex())
            {
                return 1;
            }
            else
            {
                if(2*i+2 <= GetLastElementIndex()) return 1;
                else return 0;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}

int HasAnyChild(int i)
{
    if(HasLeftChild(i) || HasRightChild(i)) return 1;
    else return 0;
}

int HasBothChild(int i)
{
    int hasLeftChild = HasLeftChild(i);
    int hasRightChild = HasRightChild(i);

    if(hasLeftChild && hasRightChild) return 1;
    else return 0;
}

int HasParent(int i)
{
    if(i>0) return 1;
    else return 0;
}
#pragma endregion

#pragma region GetXXXIndex()
int GetElementsCount()
{
    if(HasAnyElement()) return lastElementIndex + 1;
    else return EMPTY;
}
int GetLastElementIndex()
{
    if(HasAnyElement()) return lastElementIndex;
    else return EMPTY;
}

int GetParentIndex(int i)
{
    if(HasParent(i)) return (int)floor((i-1)/2);
    else return EMPTY;
}

int GetLeftChildIndex(int i)
{
    if(HasLeftChild(i)) return (2*i + 1);
    else return EMPTY;
}

int GetRightChildIndex(int i)
{
    if(HasRightChild(i)) return (2*i + 2);
    else return EMPTY;
}
#pragma endregion

#pragma region GetXXXElement()
int GetRootElement()
{
    return array[0];
}

int GetRightMostElement()
{
    if(HasAnyElement()) return array[lastElementIndex];
    else return EMPTY;
}

int GetElement(int i)
{
    if(HasAnyElement()) return array[i];
    else return EMPTY;
}

int GetParentElement(int i)
{
    if(HasParent(i)) return array[GetParentIndex(i)];
    else return EMPTY;
}

int GetLeftChildElement(int i)
{
    if(HasLeftChild(i)) return array[GetLeftChildIndex(i)];
    else return EMPTY;
}

int GetRightChildElement(int i)
{
    if(HasRightChild(i)) return array[GetRightChildIndex(i)];
    else return EMPTY;
}
#pragma endregion

#pragma region RemoveElementFromHeap()
void IterativeShiftDown(int i)
{   
    int leftOrRightChildIndex = EMPTY;
    int currentIndex = i;
    int currentElement = EMPTY;
    int childElement = EMPTY;

    while(HasAnyChild(currentIndex))
    {
        if(HasBothChild(currentIndex))
        {
            if(GetLeftChildElement(currentIndex) > GetRightChildElement(currentIndex))
            {
                leftOrRightChildIndex = GetLeftChildIndex(currentIndex);
            }
            else
            {
                leftOrRightChildIndex = GetRightChildIndex(currentIndex);
            }
        }
        else if(HasLeftChild(currentIndex))
        {
            leftOrRightChildIndex = GetLeftChildIndex(currentIndex);
        }

        currentElement = GetElement(currentIndex);
        childElement = GetElement(leftOrRightChildIndex);

        if(currentElement < childElement)
        {
            SwapElements(currentIndex, leftOrRightChildIndex);
        }

        currentIndex = leftOrRightChildIndex;
    }
}

void ShiftDownTheRootElement()
{
    IterativeShiftDown(0);
}
#pragma endregion

void Heapify()
{
    int i = 0;

    int count = GetElementsCount();

    int half = (count-2) / 2;

    for(i=half ; i>=0 ; i--)
    {
        IterativeShiftDown(i);
    }
}

void HeapSort()
{
    int i = 0;
    Heapify();

    for (i=GetLastElementIndex() ; i>=0 ; i--) 
    {
        SwapElements(i, 0);

        IterativeShiftDown(i);
    }
}

Answer 1

I studied the code and found some of the mistakes. You are correctly creating heap but while sorting you have done a few mistakes:

1. In function HeapSort You are calling IterativeShiftDown on i'th element instead you need to call it on root element so that it reaches its correct position.

2. Also after moving root element to last location you are not updating the size of heap. You need to know that in heap sort which you are doing in place we have one part of array as heap and other part as sorted part. But you are not decreasing size of heap so heap extends beyond the heap to the sorted region so it again chooses larger element which are in the sorted part and leads to formation of heap again.

Replace your HeapSort function with this it will work:

void HeapSort()
{
    int i = 0;
    Heapify();

    int size=GetLastElementIndex();

    for (i=size ; i>=0 ; i--) 
    {
        SwapElements(i, 0);
        lastElementIndex--;

        IterativeShiftDown(0); //shift the root down
    }

    lastElementIndex=size;
}