Heap Sort Algorithm – Explanation and Implementation

Heap Sort is comparison based sorting algorithm. It uses binary heap data structure. Heap Sort can be assumed as improvised version of Selection Sort where we find the largest element and place it at end index. But unlike selection sort and like quick sort its time complexity is O(n*logn). Heap sort is an in-place sorting algorithm but is not a stable sort.

Before continuing with the algorithm lets get familiar to some frequent terms use in this algorithm and this post as well.

Heap Property -> A data structure in which all nodes of the heap is either greater than equal to its children or less than equal to its children.
Max-Heapify -> Process which satisfy max-heap property (A[parent[i]] >= A[i]). Here larger element is stored at root.
Min-Heapify -> Process which satisfy min-heap property (A[parent[i]] <= A[i]). Here smaller element is stored at root.

How Heap sort works –

Heap Sort algorithm inserts all elements (from an unsorted array) into a heap then swap the first element (maximum) with the last element(minimum) and reduce the heap size (array size) by one because last element is already at its final location in the sorted array. Then we heapify the first element because swapping has broken the max heap property. We continue this process until heap size remains one.

Hereafter swapping, it may not satisfy the heap property. So, we need to adjust the location of element to maintain heap property. This process is called heapify. Here we Recursively fix the children until all of them satisfy the heap property.

Here are some key points of Heap sort algorithm –

• Heap Sort is one of the best examples of comparison based sorting algorithm.
•  Time complexity of Max-Heapify function is O(logn). Time complexity of Build-Max-Heap() function is O(n) .
• Performance of Heap Sort is O(n+n*logn) which is evaluated to O(n*logn) in all 3 cases (worst, average and best) .
• It is an in-place sorting algorithm as it requires a constant amount of additional space.
• Heap sort and Quick Sort both are in-place sorting algorithm but heap sort has an advantage over quick sort in worst case as heap sort run in O(n*logn) even in worst case.
• Heap Sort is not a stable sort, it does not retrieve the same order of equal elements in the sorted array.

Let’s understand it with an example –

Observe each step in the animation below carefully and try to visualize the concept of this algorithm.

Working of Heap sort with Max-Heapify() function:

First Step we call Build-Max-Heap() function which inserts each element of the unsorted list in a heap and maintain heap property. Once heap is built our first element of the heap is the largest element. So we swap the first element with the last element of the heap. And then, we reduce the size of a heap by one. Then we recursively call Max-Heapify() function on first element and we again get heap with first element as largest, we again swap it with the last element and reduce the size of a heap by one. We continue this process until our heap size remains one. Finally, we get our sorted list.

Pseudocode of Heap Sort

MaxHeapify(A, i)
    l = left(i)
    r = right(i)
    if l <= heap-size[A] and A[l] > A[i]
        then largest = l
        else largest = i
    if r <= heap-size[A] and A[r] > A[largest]
        then largest = r
    if largest != i
        then swap A[i] with A[largest]
        MaxHeapify(A, largest)
end func

BuildMaxHeap(A)
    heap-size[A] = length[A]
    for i = |length[A]/2| downto 1
        do MaxHeapify(A, i)
end func

HeapSort(A)
    BuildMaxHeap(A)
    for i = length[A] downto 2
        do swap A[1] with A[i]
            heap-size[A] = heap-size[A] – 1
            MaxHeapify(A, 1)
end func

Analysis of Build-Max-Heapify() function

In Build-Max-heapify() function we call Max-Heapify function about n/2 times=O(n). And running time complexity of Max-Heapify is O(h) = O(logn).So, we see that Build-Max-Heapify runs in O(n*logn).

Tighter Bound for T(BuildMaxHeap):

Cost of a call to MaxHeapify at a node depends on the height, h, of the node –> O(h).
And most of the heapification takes place at lower level. Height of node h ranges from 0 to logn.
And, at most [n/2^h+1 ] nodes are there at any height h. Therefore, running time complexity of Build-Max-Heap can be expressed as:

Asymptotic Analysis of Heap Sort

Since in Heap Sort we first call Build-Max-Heap function which takes O(n) time then we call Max-Heapify function n time, where Max-Heapify function takes O(logn) time so, total time complexity of heap-sort comes out to be O(n+n*logn) which further evaluated to O(n*logn). Summarising all this –

Time Complexity of Max-Heapify: O(logn)
Time Complexity of Build-Max-Heapify:O(n)
Time Complexity of Heap Sort-
Worst Case : O (n*logn)
Average Case : O(n*logn)
Best Case : O(n*logn)
Space Complexity: O(1) Constant space
Sorting In Place: Yes
Stable: No

Implementation of Heap Sort in various programming language

/* C implementation HeapSort */
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
// Swapping numbers using call by reference
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
 
// To Max-Heapify a subtree rooted at node i which is
// an index in A[]. n -> size of heap
// this function insure that child node
// of i node is always smaller than it.
void MaxHeapify(int A[], int n, int i)
{
    int largest = i;  // Initialize largest as root
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right  = 2*i + 2
 
    // If left child is larger than root
    if (l < n && A[l] > A[largest])
        largest = l;
    // If right child is larger than largest so far
    if (r < n && A[r] > A[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i)
    {
        //swap A[i] with A[largest]
        swap(&A[i], &A[largest]);
        // Recursively Max-Heapify the affected sub-tree
        MaxHeapify(A, n, largest);
    }
}
 
// Build-Max-Heap (rearrange array)
//Converting array A to Max-Heap
BuildMaxHeap(int A[], int n)
{
    int i;
    for (i=(n/2)-1;i>=0;i--){
        MaxHeapify(A, n, i);
        }
}
 
// main function to do Heap Sort
void heapSort(int A[], int n)
{
    int i;
    BuildMaxHeap(A, n);
    // One by one extract an element from heap
    //and get the sorted array
    for (i=n-1; i>=0; i--)
    {
        // Move top root element to end element
        swap(&A[0], &A[i]);
        //And reduce size of heap
        int heap_size= i;
        // call max heapify on the reduced heap
        MaxHeapify(A, heap_size, 0);
    }
}
 
/*  function to print an array */
void print_array(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("
");
}
 
// Driver program
int main()
{
    int A[] = {6,5,3,1,8,7,2,4};
    int n = sizeof(A)/sizeof(A[0]);
 
    printf("Unsorted array: ");
    print_array(A, n);
    printf("
");
    //Call heap sort function
    heapSort(A, n);
 
    printf("Sorted array: ");
    print_array(A, n);
    return 0;
}

package com.codingeek;
import java.util.Arrays;
 
public class HeapSort {
    int A[];
     
    private void swap(int i, int j) {
         int temp = A[i];
         A[i] = A[j];
         A[j] = temp;
     }
     
    // To Max-Heapify a subtree rooted at node i which is
    // an index in A[].  n -> size of heap
    void maxHeapify(int A[],int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int l = 2*i + 1;  // left = 2*i + 1
        int r = 2*i + 2;  // right = 2*i + 2
  
        // If left child is larger than root
        if (l < n && A[l] > A[largest])
            largest = l;
  
        // If right child is larger than largest so far
        if (r < n && A[r] > A[largest])
            largest = r;
  
        // If largest is not root
        if (largest != i)
        {
             
            swap(i,largest);
            // Recursively heapify the affected sub-tree
            maxHeapify(A,n,largest);
        }
    }
     
 // Build-Max-Heap (rearrange array)
  //Converting array A to Max-Heap
    public void BuildMaxHeap(int A[])
    {
        int n = A.length; 
        // one by one checking all root nodes
        //and calling Heapify function 
        //if they does not satisfy heap property
        for (int i = n / 2 - 1; i >= 0; i--)
            maxHeapify(A,n,i);
    }
     
    // main function to do Heap Sort
    public void heapSort(int arr[])
    {   
        this.A=arr;
        int n = A.length;
         
        BuildMaxHeap(A);
        // One by one extract an element from heap
        //and get the sorted array
        for (int i=n-1; i>=0; i--)
        {
            // Move top root element to end element
            swap(0,i);
            // call max heapify on the reduced heap
            maxHeapify(arr, i, 0);
        }
    }
  
    // Driver program
    public static void main(String args[])
    {
        int arr[] = {6,5,3,1,8,7,2,4};
      //print unsorted array using Arrays.toString()
        System.out.print("Unsorted array: ");
        System.out.println(Arrays.toString(arr));
  
        HeapSort ob = new HeapSort();
        ob.heapSort(arr);
  
        System.out.print("Sorted array: ");
        //print sorted array
          System.out.println(Arrays.toString(arr)); 
    }
}

Output:-
Unsorted array:  6 5 3 1 8 7 2 4 
Sorted array:    1 2 3 4 5 6 7 8

That’s all for heap sort, one of the most famous comparison based sorting algorithm. As a programmer, one should be aware of this algorithm and it is quite fast with time complexity of O(n log n) in all three cases. It is better than Merge Sort as it is in-place sorting Algorithm. And it is better than Quick Sort because it takes O(n*logn) even in the worst case where as quick sort takes O(n*n).
Although in practise heap sort run slower than quick sort and merge sort on modern computers.
Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.(Wiki)

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning… Happy Learning.. 🙂

Recommended -