Heaps & Priority Queues7 min read

Heaps

Always know the smallest (or largest) in \(O(1)\) — with \(O(\log n)\) updates

insert: \(O(\log n)\)extract min/max: \(O(\log n)\)peek min/max: \(O(1)\)build: \(O(n)\)space: \(O(n)\)

Imagine a VIP lounge where the most important guest is always at the front of the line. When that guest leaves, the next most important person instantly moves to the front. New arrivals politely shuffle up or stay back based on their importance. That's a heap — a priority queue where the most urgent item is always instantly accessible.

Technically, a heap is a complete binary tree stored compactly in an array, satisfying one simple rule:

Min-Heap: every parent ≤ its children (root holds the minimum)
Max-Heap: every parent ≥ its children (root holds the maximum)

The tree is "complete" — all levels are fully filled except possibly the last, which fills left to right. This lets us use a plain array with no pointers: for node at index i, its left child is at 2i+1, right child at 2i+2, and parent at (i-1)//2.

◈ Insert and extract

← → arrow keys to step · click elements to interact

Heap Operations

import heapq

# Min-heap
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(h[0])              # peek min: 1
print(heapq.heappop(h))  # extract:  1
print(h[0])              # new min:  3

# Build heap in O(n)
arr = [9, 4, 7, 2, 6]
heapq.heapify(arr)
print(arr[0])            # 2

Output

Sift Up — after inserting

Insert a new value at the end of the array (next open position in the tree). Then compare it with its parent. If the heap property is violated, swap with parent and repeat. This "sift up" (or "bubble up") continues until the property holds or the element reaches the root. At most log n swaps — one per level.

Sift Down — after extracting

The root (min/max) is what we want. Remove it, then move the last element to the root to keep the array compact. Now sift down: compare with both children, swap with the smaller child (min-heap), repeat until the heap property holds. Again, at most log n swaps.

Build Heap in \(O(n)\)

Inserting n elements one by one costs \(O(n \log n)\). But there is a smarter way: start from the last non-leaf node (index n//2 - 1) and sift down each node toward the leaves. The math works out that the total work is \(O(n)\) — this is the heapify algorithm used by heap sort.

Note: A heap is NOT a fully sorted structure — only the root is guaranteed to be the min/max. The relative order of other elements is only partially constrained. This is what makes build-heap \(O(n)\) instead of \(O(n \log n)\).

Complexity

Peek min/max (root)Root is always the min (or max) — just read index 0

Instant\(O(1)\)

InsertAppend then sift up at most log n levels

Log n\(O(\log n)\)

Extract min/maxRemove root, move last to root, sift down

Log n\(O(\log n)\)

Build heap (heapify)Smarter than n inserts — sift down from leaves

Linear!\(O(n)\)

Search arbitraryHeap gives no order guarantees beyond parent ≤ children

Linear\(O(n)\)

SpaceStored as a flat array — no pointer overhead

Linear\(O(n)\)

K Smallest Elements

import heapq

arr = [7, 2, 9, 1, 5, 3, 8]
k = 3

# K smallest — built-in
print(heapq.nsmallest(k, arr))  # [1, 2, 3]

# K largest — min-heap of size k
heap = []
for x in arr:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)  # evict smallest
print(sorted(heap))            # [7, 8, 9]

Output

[1, 2, 3]
[7, 8, 9]

Challenge

Quick check

In a min-heap stored as an array, where is the minimum element always found?

Heap Sort

Sort in-place with guaranteed \(O(n \log n)\) — no extra memory needed

→

Priority Queue Patterns

K-th largest, merge K lists, top-K frequent — solved with a small heap

→

Two-Heap Pattern

Split the data in half — find the median in \(O(1)\) always

→

Load BalancingSystem Design

Spread the work so no single server drowns

→