HeapSort Algorithm Tutorial and Implementation

HeapSort is an efficient (O(N*lognN) time) comparison-based sorting algorithm based on Binary Heaps. It works by dividing input unsorted array into the sorted and unsorted region and iteratively keeps on decreasing the unsorted region and increasing the sorted region and stops when there is no more unsorted region left.

Binary Heap

A Binary Heap is a form of Binary Tree with the following additional properties –

1. A Binary Heap is a complete Binary tree with all levels except the last level is completely filled. The last level of the tree is not completely full and nodes at each level are filled from left to right.
2. A heap can be a Max-Heap or a Min-Heap. In Max-Heap the root node is the largest node and all nodes at a level will be strictly less than or equal to the parent node. In Max-Heap the root node is the smallest node and nodes at a level will be strictly greater than or equal to the parent node.

HeapSort Algorithm

The heapsort algorithm sorts elements of a given array using the following two phases repeatedly:

1. Convert the given array into the Max-Heap (or Min-Heap) using the Build Heap function.
2. Now the largest element will be present at the root Node. Replace it with the last node of the Heap, decrease the size of heap by one, and call the Heapify function again on the root node.
3. Repeat step 2 until the entire array is not sorted.

Let’s understand the HeapSort algorithm with an example

Step 1: Suppose we are given an array representation [11, 18, 9, 25, 24, 27, 16] of a Binary Tree, start by first converting it into a Binary Heap, using Build Heap function as shown below.

Step 2: Replace the last node of the Heap (11) with the root node (27). After this step, the last node present at the root will violate the property of the Heap, hence we have to perform the Heapify (11) to convert it back to a max-heap. Since the original root node (27) is at its correct position we are only required to sort remaining n-1 elements only. Hence we will decrease the heap size by 1.

Step 3: Again replace the last node of the Heap(Note, heap size has now reduced by 1) with the root node and perform Heapify on the root node.

[ 9, 11, 16, 18, 24, 25, 27] is a resultant sorted array generated using the HeapSort algorithm.

HeapSort(arr, size)
{
    for(i=size-1; i>0; i--)
    {
         swap(arr[0], arr[i])
         heapify(arr, 0, i) 
    }
}

Implementation of HeapSort

#include <bits/stdc++.h> 
using namespace std; 
   
int heapify(int arr[], int i, int n) 
{ 
    int largest = i; 
    int left = 2 * i + 1; 
    int right = 2 * i + 2; 
  
    if (left < n && arr[left] > arr[largest]) 
        largest = left; 
  
    if (right < n && arr[right] > arr[largest]) 
        largest = right; 

    if (largest != i) { 
        swap(arr[i], arr[largest]); 
        heapify(arr, largest, n); 
    }

    return 0; 
} 
  
int buildHeap(int arr[], int n) 
{ 
    int last_parent = (n / 2) - 1; 
  
    for (int i = last_parent; i >= 0; i--) { 
        heapify(arr, i, n); 
    }
    return 0; 
} 

int heapSort(int arr[], int n){

    buildHeap(arr, n);

    for(int i=n-1; i>=0; i--){
        swap(arr[0], arr[i]);
        heapify(arr, 0, i);
    }   

    return 0;
}

int main() 
{ 
    int arr[] = {9, 11, 16, 18, 24, 25, 27}; 
  
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout<<"Sorted array is -"<<endl;
    for (int i = 0; i < n; ++i) 
        cout << arr[i] << " "; 
    cout <<endl; 

    return 0; 
} 

Output

Sorted array is - 
9 11 16 18 24 25 27

Time Complexity

HeapSort works by calling Heapify function N times, where N is the number of elements in a Heap and the time complexity of Heapify function is O(log N), hence the time complexity for running HeapSort algorithm is O(N*lognN).

HeapSort properties at a glance:

1. Best & worst-case time complexity = O(N*logN)
2. Auxiliary space requirement = O(1)
3. Number of comparisons required = O(N²)
4. HeapSort is an in-place sorting algorithm
5. Heap Sort is not a stable sort
6. Heapsort typically runs faster in practice on machines with small or slow data caches
7. Heapsort can be adapted to operate on doubly linked lists with only O(1) extra space overhead