Back to DSA Course

A Heap is a specialized, complete binary tree data structure that satisfies the heap property.

• Complete binary tree: every level is fully filled except possibly the last level, which is filled from left to right. This property means a heap can be stored efficiently in a flat array with no wasted space — for any node at index i, its left child is at index 2i+1 and right child at 2i+2.

• Max-Heap: the value of each parent node is greater than or equal to its children. The maximum element is always at the root.

• Min-Heap: the value of each parent node is less than or equal to its children. The minimum element is always at the root.

The original statement "child node must be less than parent node" only describes a max-heap. Both max-heap and min-heap are valid heap types.

Heap Sort works in two phases:

1. Build a max-heap from the input array in O(n) time (heapify from the last non-leaf node upwards).
2. Extract the maximum repeatedly: swap the root (max) with the last element, reduce the heap size by 1, and re-heapify down from the root. Repeat n-1 times.

package com.praveen.sort;

public class HeapSort {

    public static void main(String[] args) {
        int[] num = { 90, 24, 46, 35, 32 };
        heapSort(num);
        for (int i : num) {
            System.out.print(i + " ");
        }
    }

    private static void heapSort(int[] num) {
        int len = num.length;

        // Phase 1: Build max-heap.
        // Start from the last non-leaf node (index len/2 - 1) and heapify downwards.
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(num, len, i);
        }

        // Phase 2: Extract elements from the heap one by one.
        // Swap root (largest) with the last element, reduce heap size, re-heapify.
        for (int i = len - 1; i >= 0; i--) {
            int temp = num[0];
            num[0] = num[i];
            num[i] = temp;
            heapify(num, i, 0);
        }
    }

    // Heapify a subtree rooted at index i, for a heap of size len.
    // Ensures the max-heap property: parent >= both children.
    private static void heapify(int[] num, int len, int i) {
        int largest = i;        // assume root is largest
        int li = 2 * i + 1;    // left child index
        int ri = 2 * i + 2;    // right child index

        if (li < len && num[li] > num[largest]) {
            largest = li;
        }
        if (ri < len && num[ri] > num[largest]) {
            largest = ri;
        }
        if (largest != i) {
            int temp = num[i];
            num[i] = num[largest];
            num[largest] = temp;
            // Recursively heapify the affected subtree
            heapify(num, len, largest);
        }
    }
}

Output

24 32 35 46 90

Complexity

Case     | Time       | Space
---------|------------|-----------------------------
Best     | O(n log n) | O(log n) — recursion stack
Average  | O(n log n) | O(log n)
Worst    | O(n log n) | O(log n)

Heap sort has guaranteed O(n log n) time in all cases and sorts in-place (O(log n) auxiliary space from the recursive heapify call stack, or O(1) with an iterative heapify). Unlike merge sort, it does not require additional arrays.

However, heap sort is not stable — equal elements may change their relative order during sorting. It also has poor cache performance compared to quicksort or merge sort, because heapify accesses non-contiguous memory locations, leading to more cache misses. This is why quicksort tends to outperform heap sort in practice despite having a worse worst-case complexity.

Heaps are also useful as a standalone data structure — Java's PriorityQueue is backed by a min-heap and supports O(log n) insertion and O(log n) removal of the minimum element.