Offensive Security Researcher & Quantum Cryptography Analyst

Heap Sort Algorithm: Working, Explanation, and Binary Heap-Based Sorting

Abdul Wahab Junaid
heap sort algorithm and working of this algorithm

heap sort algorithm and working of this algorithm

I see heap sort as the algorithm that combines the best guarantees of selection sort with the efficiency of a smart data structure. It is a comparison-based sorting algorithm built entirely around the binary heap — a specialized tree-based structure that lets me find the maximum (or minimum) element in constant time and remove it in logarithmic time. What makes heap sort stand out to me is that it delivers a guaranteed O(n log n) time complexity in every case, just like merge sort, but does so completely in place, without needing any extra array. That combination of speed guarantees and memory efficiency is rare among sorting algorithms.

History and Background

Heap sort was invented by J.W.J. Williams in 1964, who introduced the binary heap data structure in the same paper as a way to implement an efficient priority queue for sorting. Shortly after, Robert W. Floyd improved the algorithm’s efficiency by introducing a faster way to build the heap in linear time (the “bottom-up heap construction” method), which became the standard technique used in nearly all practical heap sort implementations today. Heap sort has remained a staple of computer science curricula because it elegantly demonstrates how a well-chosen data structure can transform an already-known algorithm (selection sort) into something asymptotically much faster.

Problem Statement

I need a sorting algorithm that guarantees O(n log n) performance in the worst case, unlike quick sort, while also sorting in place, unlike merge sort. Heap sort solves this by using a binary heap to efficiently and repeatedly extract the maximum element from the unsorted portion of the array, replacing selection sort’s slow linear scan for the maximum with a much faster logarithmic-time heap operation.

Core Concepts

How It Works

I break heap sort into two main phases:

  1. Build the max-heap: I convert the entire input array into a valid max-heap, which places the largest element at the root (index 0).
  2. Extract elements repeatedly: I swap the root (the current maximum) with the last element of the heap, shrink the heap size by one, and then heapify the root to restore the max-heap property. I repeat this until the heap size is reduced to one, at which point the array is fully sorted in ascending order.

Working Principle

The core mechanism I rely on is that a max-heap always guarantees the largest remaining element sits at the root, accessible in O(1) time. By repeatedly swapping this root with the last unsorted position and then “sinking” the newly displaced element down through the heap using the heapify operation, I restore the heap property in O(log n) time rather than the O(n) time a linear scan would require. This is exactly what separates heap sort from selection sort: both algorithms repeatedly extract the maximum and place it at the end, but heap sort uses a smarter structure to make each extraction dramatically faster.

Mathematical Foundation

Building the initial heap takes O(n) time, which I can derive by noting that heapifying a node at height h costs O(h), and the number of nodes at height h in a complete binary tree is roughly $n / 2^{h+1}$. Summing this cost across all heights gives:

$$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot O(h) = O(n) \sum_{h=0}^{\log n} \frac{h}{2^h} = O(n)$$

since the series $\sum h/2^h$ converges to a constant. After building the heap, I perform n-1 extraction operations, and each extraction requires a heapify call costing O(log n):

$$T_{extract}(n) = \sum_{i=1}^{n-1} O(\log i) = O(n \log n)$$

Combining both phases, the total time complexity is:

$$T(n) = O(n) + O(n \log n) = O(n \log n)$$

The height of the heap, which bounds each heapify call, is:

$$h = \lfloor \log_2 n \rfloor$$

Diagrams

flowchart TD
    A[Start: Unsorted array] --> B[Build max-heap from array]
    B --> C[Swap root max element with last element]
    C --> D[Reduce heap size by one]
    D --> E[Heapify root to restore max-heap property]
    E --> F{Heap size greater than one?}
    F -->|Yes| C
    F -->|No| G[Output: Sorted array]

Pseudocode

HEAP-SORT(A)
    n = length(A)
    BUILD-MAX-HEAP(A, n)

    for i = n - 1 down to 1
        swap A[0] with A[i]
        HEAPIFY(A, i, 0)

BUILD-MAX-HEAP(A, n)
    for i = floor(n/2) - 1 down to 0
        HEAPIFY(A, n, i)

HEAPIFY(A, n, i)
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < n and A[left] > A[largest]
        largest = left
    if right < n and A[right] > A[largest]
        largest = right

    if largest != i
        swap A[i] with A[largest]
        HEAPIFY(A, n, largest)

Step-by-Step Example

I will sort [4, 10, 3, 5, 1].

Build max-heap: Starting from index floor(5/2)-1 = 1 down to 0.

Heap is now: [10, 5, 3, 4, 1]

Extraction phase:

Final sorted output: [1, 3, 4, 5, 10]

Time Complexity

Space Complexity

Heap sort is fully in-place, requiring only O(1) additional space for temporary variables during swaps (or O(log n) if implemented recursively, due to the heapify call stack, though this can be converted to an iterative version to achieve true O(1) auxiliary space). It needs no separate array structure since the heap is represented directly within the original array.

Correctness Analysis

I prove heap sort’s correctness in two parts. First, the build-heap phase correctly establishes the max-heap property for the entire array — this follows inductively from the fact that heapify correctly restores the max-heap property at any node, given that its subtrees already satisfy it, and I process nodes bottom-up so this precondition always holds. Second, the extraction phase maintains a loop invariant: at the start of each iteration, A[0..i] forms a valid max-heap, and A[i+1..n-1] contains the largest (n-i-1) elements of the array, sorted correctly. Swapping the root (guaranteed maximum of the current heap) to position i and reducing the heap size extends this invariant, since the root of a max-heap is always its largest element. When the loop terminates, the invariant guarantees the entire array A[0..n-1] is sorted in ascending order.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

// Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify a subtree rooted at index i, where n is the heap size
void heapify(int arr[], int n, int i) {
    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, n, largest);  // recursively fix the affected subtree
    }
}

// Main heap sort function
void heapSort(int arr[], int n) {
    // Build max-heap: heapify all non-leaf nodes, bottom-up
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements one by one from the heap
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);   // move current root (max) to the end
        heapify(arr, i, 0);       // heapify reduced heap
    }
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Sample Input and Output

Input: [4, 10, 3, 5, 1]

Output: Sorted array: 1 3 4 5 10

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version