Heap sort explained with simple example

Heap sort is one of the fastest sorting algorithm, which works on Divide and Conquer algorithm. In this sorting algorithm, all the data elements are inserted into a heap (max or min) and then removes item from the root of the heap will give the sorted(descending or ascending) data list.

Pros:
1) Faster algorithm and best performance O(nlogn).
2) Simple implementation.
3) No extra space is needed.
4) Good for cases to find biggest/smallest or top k biggest/smallest element finding kind of scenarios.

Cons:
1) Not a stable sort means position of relative identical data items is not guaranteed.

Let’s revisit the property of Heap, which will help us to understand heap sort algorithm more effectively.

A Heap is a tree in which value of a node is always >= (or <=) than the value of its children.

Algorithm explained via example:

Let us take an example array “76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59”. Now we will run through this array with heap sort algorithm to understand how it works.

First, we have to create the Heap(max) from the data input which is as follows:
100, 97, 65, 38, 76, 59, 44, 4, 33, 23, 1, 10

Replace the top element with the last element(effectively using memory) and then adjust to ensure heap property satisfied.
97, 76, 65, 38, 23, 59, 44, 4, 33, 10, 1, 100

Repeating the above step and we will see the list is being sorted in following manner.
76, 38, 65, 33, 23, 59, 44, 4, 1, 10, 97, 100
65, 38, 59, 33, 23, 10, 44, 4, 1, 76, 97, 100
59, 38, 44, 33, 23, 10, 1, 4, 65, 76, 97, 100
44, 38, 10, 33, 23, 4, 1, 59, 65, 76, 97, 100
38, 33, 10, 1, 23, 4, 44, 59, 65, 76, 97, 100
33, 23, 10, 1, 4, 38, 44, 59, 65, 76, 97, 100
23, 4, 10, 1, 33, 38, 44, 59, 65, 76, 97, 100
10, 4, 1, 23, 33, 38, 44, 59, 65, 76, 97, 100
4, 1, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100

Now the lis is sorted.

Let’s have a look at the sample program for Heap sort.

void printArray(int a[] )
{
	for (int i = 0; i < 12; i++)
	{
		cout << a[i] << ", ";
	}
	cout << endl;
}

void heapify(int array[], int n)
{
	int item, i, j, k;

	for (k = 1; k<n; k++)
	{
		item = array[k];
		i = k;
		j = (i - 1) / 2;

		while ((i>0) && (item>array[j]))
		{
			array[i] = array[j];
			i = j;
			j = (i - 1) / 2;
		}
		array[i] = item;
	}
}

void adjust(int array[], int n)
{
	int item, i, j;

	j = 0;
	item = array[j];
	i = 2 * j + 1;

	while (i <= n - 1)
	{
		if (i + 1 <= n - 1)
			if (array[i] < array[i + 1])
				i++;
		if (item < array[i])
		{
			array[j] = array[i];
			j = i;
			i = 2 * j + 1;
		}
		else
			break;
	}
	array[j] = item;
}

void heapsort()
{
	int i, t;
	int a[] = { 76,4,65,33,23,10,44,38,97,100,1,59 };
	cout << "Heap Sort" << endl;
	cout << "Initial array" << endl;
	printArray(a);
	int n = 12;

	heapify(a, n);
	printArray(a);
	for (i = n - 1; i>0; i--)
	{
		t = a[0];
		a[0] = a[i];
		a[i] = t;
		adjust(a, i);
		printArray(a);
	}
}

int main()
{
    heapsort();
}

Output of the above program is as follows:

Heap Sort
Initial array
76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59,
100, 97, 65, 38, 76, 59, 44, 4, 33, 23, 1, 10,
97, 76, 65, 38, 23, 59, 44, 4, 33, 10, 1, 100,
76, 38, 65, 33, 23, 59, 44, 4, 1, 10, 97, 100,
65, 38, 59, 33, 23, 10, 44, 4, 1, 76, 97, 100,
59, 38, 44, 33, 23, 10, 1, 4, 65, 76, 97, 100,
44, 38, 10, 33, 23, 4, 1, 59, 65, 76, 97, 100,
38, 33, 10, 1, 23, 4, 44, 59, 65, 76, 97, 100,
33, 23, 10, 1, 4, 38, 44, 59, 65, 76, 97, 100,
23, 4, 10, 1, 33, 38, 44, 59, 65, 76, 97, 100,
10, 4, 1, 23, 33, 38, 44, 59, 65, 76, 97, 100,
4, 1, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,

Algorithm performance:

Time complexity:
Heap sort is not affected by data distribution.Time complexity for best and worst both case is O(nlogn).

Space complexity:
Since, no extra space is needed for this sorting algorithm. Hence, Space complexity is O(1).