Heap Sort Algorithm (With Code in Python and C++)

What is Heap Sort Algorithm?

Heap Sort is one of the popular and faster sorting algorithms. It’s built on the complete binary tree data structure. We will search for the maximum element and put it on the top for the max heap. We will put it on the parent node of the binary tree.

Let’s say an array is given, data = [10,5, 7, 9, 4, 11, 45, 17, 60].

In the array, if i-th (i=0,1,2,3 …) index is a parent node then, (2i+1) and (2i+2) will be the left and right children. Creating a complete binary tree with this array will look like this:

We will do the heapify process from the beginning to the end of the array. Initially, if we convert the array to a tree, it will look like the above. We can see that it’s not maintaining any heap property (min-heap or max heap). We will get the sorted array by doing the heapify process for all the nodes.

Application of Heap Sort

Here’s some usage of the heap sort algorithm:

• Construction of “Priority Queues” needs heap sort. Because heapsort keeps the element sorted after each insertion is being made.
• Heap Data Structure is efficient in finding the k^th largest element in a given array.
• Linux Kernel uses the heap sort as a default sorting algorithm as it has O (1) space complexity.

Create Heap Sort with Example

Here, we will construct a max heap from the following complete binary tree.

The leaf nodes are 17, 60, 4, 11, and 45. They don’t have any child nodes. That is why they are leaf nodes. So, we will start the heapify method from their parent node. Here are the steps:

Step 1) Select the left-most sub-tree. If the child nodes are greater, swap the parent node with the child node.

Here the parent node is 9. And the child nodes are 17 and 60. As, 60 is the largest, 60 and 9 will be swapped to maintain the max heap.

Step 2) Now, the left-most subtree is heapified. The next parent node is 7. This parent has two child nodes, and the largest is 45. So, 45 and 7 will be swapped.

Step 3) Nodes 60 and 4 have the parent node 5. As “5” is smaller than the child node 60, it will be swapped.

Step 4) Now, node 5 has the child node 17,9. This is not maintaining the max heap property. So, 5 will be replaced with 17.

Step 5) Node 10 will be swapped with 60, then swapped with 17. The process will look like the following.

Step 6) Up to step 5, we created the max heap. Every parent node is larger than its child nodes. The root node has the maximum value (60).

Note: To create the sorted array, we need to replace the max valued node with its successor.

This process is called “extract max”. As 60 is the max node, we will fix its position to the 0th index and create the heap without node 60.

Step 7) As 60 is removed, then the next maximum value is 45. We will do the process “Extract Max” again from node 45.

This time we will get 45 and replace the root node with its successor 17.

We need to perform “Extract Max” until all the elements are sorted.

After doing these steps until we extract all the max values, we will get the following array.

What is Binary Heap?

A Binary Heap is a kind of complete binary tree data structure. In this kind of tree structure, the parent node is either greater or smaller than the child nodes. If the parent node is smaller, then the heap is called the “Min Heap” and if the parent node is greater, the heap is called the “Max Heap”.

Here’re examples of min heap and max heap.

In the above figure, if you notice the “Min Heap”, the parent node is always smaller than its child nodes. At the head of the tree, we can find the smallest value 10.

Similarly, for the “Max Heap”, the parent node is always larger than the child nodes. The maximum element is present at the head node for the “Max Heap”.

What is “Heapify”?

“Heapify” is the principle of the heap that ensures the position of the node. In Heapify, a max heap always maintains a relationship with parent and child, and that is parent node will be larger than the child nodes.

For example, if a new node is added, we need to reshape the heap. However, we might need to change or swap the nodes or rearrange array. This process of reshaping a heap is called the “heapify”.

Here is an example of how heapify works:

Here are the steps for heapify:

Step 1) Added node 65 as the right child of node 60.

Step 2) Check if the newly added node is greater than the parent.

Step 3) As it’s greater than the parent node, we swapped the right child with its parent.

How to build the Heap

Before building the heap or heapify a tree, we need to know how we will store it. As the heap is a complete binary tree, it’s better to use an array to hold the data of the heap.

Let’s say an array contains a total of n elements. If “i”th index is a parent node, then the left node will be at index (2i+1), and the right node will be at index (2i+2). We are assuming that the array index begins from 0.

Using this, let’s store a max heap to an array-like following:

The heapify algorithm maintains the heap property. If the parent does not have the extreme value (smaller or greater), it will be swapped with the most extreme child node.

Here are the steps to heapify a max heap:

Step 1) Start from the leaf node.

Step 2) Find the maximum between the parent and children.

Step 3) Swap the nodes if the child node has a larger value than the parent.

Step 4) Go one level up.

Step 5) Follow steps 2,3,4 until we reach index 0 or sort the entire tree.

Here’s the pseudo-code for recursive heapify (max heap):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Pseudo Code for Heap Sort

Here’s the pseudo-code for the heap sort algorithm:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Example of Heap Sort Code in C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Output:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Example of Heap Sort Code in Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Output:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Time and Space Complexity analysis of Heap Sort

There’s Time complexity and Space complexity that we can analyze for the heap sort. For time complexity we’ve the following cases:

1. Best Case
2. Average Case
3. Worst Case

The heap is implemented on a complete binary tree. So, at the bottom level of the binary tree, there will be the maximum number of nodes. If the bottom level has n nodes, then the above level will have n/2 nodes.

In this example, Level 3 has four items, level 2 has two items, and level 1 has one item. If there is a total n number of items, the height or total level will be Log₂(n). So, inserting a single element could take a maximum of Log(n) iterations.

When we want to take the maximum value from the heap, we just take the root node. Then again, run the heapify. Each heapify takes Log₂(n) time. Extracting the maximum takes O(1) time.

Best Case Time Complexity for Heap Sort Algorithm

When all the elements are already sorted in the array, it will take O(n) time to build the heap. Because if the list is sorted then inserting an item will take the constant time that is O(1).

So, it will take O(n) time to create a max-heap or min-heap in the best case.

Average Case Time Complexity for Heap Sort Algorithm

Inserting an item or extracting a maximum costs O(log(n)) time. So, the average case time complexity for the heap sort algorithm is O(n log(n)).

Worst Case Time Complexity for Heap Sort Algorithm

Similar to the average case, in the worst-case scenario, we might to perform heapify n times. Each heapify will cost O(log(n)) time. So, the worst-case time complexity will be O(n log(n)).

Space Complexity for Heap Sort Algorithm

Heap sort is an in-place designed algorithm. This means that no extra or temporary memory is needed to perform the task. If we see the implementation, we will notice that we used swap () to perform the exchange of the nodes. No other list or array was needed. So, the space complexity is O(1).

FAQs