Heaps & Priority Queues5 min read

Heap Sort

Sort in-place with guaranteed \(O(n \log n)\) — no extra memory needed
build heap: \(O(n)\)sort: \(O(n \log n)\)space: \(O(1)\) in-place

Heap sort elegantly combines the two key heap operations into a sorting algorithm. It has the best-of-both-worlds profile of merge sort's \(O(n \log n)\) guarantee with quicksort's in-place \(O(1)\) extra space — but with a catch we'll get to.

The algorithm has two phases:

  1. Build a max-heap from the input array using Floyd's heapify algorithm — \(O(n)\)
  2. Extract repeatedly: swap the root (current maximum) with the last element, shrink the heap boundary by 1, then sift down the new root — repeat n-1 times — \(O(n \log n)\)

Each extraction places the current maximum at the end of the array, building a sorted sequence from the right. No extra array needed — just the original array and a moving "heap boundary".

◈ Watch heap sort

← → arrow keys to step · click elements to interact

Heap Sort

def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr


arr = [12, 11, 13, 5, 6, 7]
print(heap_sort(arr))  # [5, 6, 7, 11, 12, 13]
Output
[5, 6, 7, 11, 12, 13]

Step-by-step on [4, 1, 3, 2, 6]

pseudocode
1
2
3
4
5
6
7
8
Input:     [4, 1, 3, 2, 6]
Max-heap:  [6, 4, 3, 2, 1]   (after heapify)


Extract 6: swap → [1, 4, 3, 2, | 6], sift down → [4, 2, 3, 1, | 6]
Extract 4: swap → [1, 2, 3, | 4, 6], sift down → [3, 2, 1, | 4, 6]
Extract 3: swap → [1, 2, | 3, 4, 6], sift down → [2, 1, | 3, 4, 6]
Extract 2: swap → [1, | 2, 3, 4, 6]
Result:    [1, 2, 3, 4, 6]

Why not use heap sort everywhere?

Despite its perfect asymptotic profile, heap sort is rarely used in practice compared to quicksort or merge sort. The reason is cache performance.

Quicksort accesses memory sequentially during partition. Heap sort's sift-down jumps between parents and children at positions i, 2i+1, 2i+2 — for large arrays these are cache misses, making heap sort 2-5× slower in practice even though it's the same Big-O.

Heap sort vs merge sort vs quicksort

  • Heap sort: \(O(n \log n)\) always, \(O(1)\) space, cache-unfriendly, not stable
  • Merge sort: \(O(n \log n)\) always, \(O(n)\) space, cache-friendly (sequential), stable
  • Quicksort: \(O(n \log n)\) average, \(O(n^2)\) worst, \(O(\log n)\) stack, very cache-friendly, not stable
Note: Heap sort is the go-to answer when asked for an in-place \(O(n \log n)\) worst-case sort. In an interview, saying 'I would use merge sort for stability, but heap sort if space is the constraint' shows you understand the real tradeoffs.

Complexity

Build max-heapFloyd's heapify — sift down from all non-leaves
Linear\(O(n)\)
n-1 extraction stepsEach sift-down is \(O(\log n)\), done n-1 times
n log n\(O(n \log n)\)
Total sortBest, average, and worst case — always the same
n log n\(O(n \log n)\)
SpaceSorts in the original array; only recursion uses \(O(\log n)\) stack
Constant!\(O(1)\)

K Largest Elements with a Heap

import heapq


def k_largest(arr, k):
    # Use min-heap of size k
    return heapq.nlargest(k, arr)


print(k_largest([3, 1, 4, 1, 5, 9, 2, 6, 5], 3))  # [9, 6, 5]


# Manual min-heap approach:
def k_largest_manual(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    for v in arr[k:]:
        if v > heap[0]:
            heapq.heapreplace(heap, v)
    return sorted(heap, reverse=True)


print(k_largest_manual([3, 1, 4, 1, 5, 9, 2, 6, 5], 3))  # [9, 6, 5]
Output
[9, 6, 5]
[9, 6, 5]
Challenge

Quick check

What is the first phase of heap sort?

Continue reading

Heaps
Always know the smallest (or largest) in \(O(1)\) — with \(O(\log n)\) updates
→
Priority Queue Patterns
K-th largest, merge K lists, top-K frequent — solved with a small heap
→
Binary Trees
A family tree where every parent has at most two children
→