Heap Sort in C: Basics & Code Snippet

Few of the sorting techniques like the bubble sort, selection or the insertion sort are good enough for sorting small number of element, while heap sort is used to large number of elements, in a faster way. It’s simple as well, but all it consumes is the additional memory.

Before we get into heap sort technique, let us learn something about the heap data structure, which is used in heap sort. Top element that is present in the heap indicates the next in the line as in the order either it may be highest or the lowest.

Firstly, we will have to create a heap and then go on adding elements to the heap and once you want to delete it then you can easily remove from the heap and in a sorted order as such.

There are two things here one has to worry about –

a. that is the time taken to create the heap, and
b. the time taken to add and remove the element from the heap.

Well, this is quite faster when compared to any of the other sorting techniques.

One of the major disadvantages associated with this technique is that it’s not stable for equal elements, as in it does not preserve the original order. F

or instance if we consider having a list of messages in your inbox then, then you would want the sort by both time and date as well as in an alphabetical order. Then in such cases, you can first sort it as per the date and time and then sort as per the alphabetical order.

Let us illustrate the above scenario with an example:

From: a@qwerty.com sent: 1/1/2011
From: b@qwerty.com sent: 1/1/2011
From: c@qwerty.com sent: 2/9/2009
After sorting using heap sort
From: c@qwerty.com sent: 2/9/2009
From: b@qwerty.com sent: 1/1/2011
From: a@qwerty.com sent: 1/1/2011

As we can see that “b” is ahead of “a” which does not happen in any other sorting techniques as such which indicates that the sort is unstable. A stable sort should look like:

From: c@qwerty.com sent: 2/9/2009
From: a@qwerty.com sent: 1/1/2011
From: b@qwerty.com sent: 1/1/2011

Code Snippet to Implement Heap Sort in C Programming Language

void HSort(int num[], int size)
{
int j, temp;
for (j = (size / 2); j >= 0; j–)
shift(num, j, size – 1);
for (j = size-1; j >= 1; j–)
{
temp = num[0];
num[0] = num[i];
num[i] = temp;
shift(num, 0, i-1);
}
}
void shift(int num [], int head, int tail)
{
int ok, max, temp;
ok = 0;
while ((head*2 <= tail) && (!ok))
{
if (head*2 == tail)
max = head * 2;
else if (num [head * 2] > num [head * 2 + 1])
max= head * 2;
else
max = head * 2 + 1;

if (num [head] < num[max])
{
temp = num[head];
num[head] = num [max];
num[max] = temp;
head = max;
}
else
ok = 1;
}
}

So, that was a simple illustration of heap sort in c – stay tuned for more useful code snippets!