-
Notifications
You must be signed in to change notification settings - Fork 0
009 — Heaps and Priority Queues
Every structure so far either has no ordering at all (arrays, hash maps), or a total ordering (BSTs, sorted arrays) — every element knows exactly where it sits relative to every other element. A heap makes a deliberate trade: it gives up total ordering to get something faster — instant access to just the most urgent element.
Picture a hospital emergency room. Patients don't get treated in the order they arrived (that's a queue, Chapter 06) — they get treated in order of severity. A patient with a heart attack who just walked in gets seen before someone with a sprained ankle who's been waiting two hours.
- 🚑 The triage nurse doesn't need to know the exact ranking of all 40 people in the waiting room.
- 🩺 She only ever needs to know one thing, instantly: who's most critical right now.
- 🔄 The moment that patient is treated and removed, the "who's most critical now" question needs a fresh, fast answer — again, without re-sorting the entire room.
That's a heap: not a fully sorted list, just a structure that keeps the most extreme element (min or max) at instant reach, and cheaply restores that property after every change.
A heap is a binary tree with one relaxed rule, the heap property:
- Min-heap: every parent is less than or equal to its children. The smallest element is always at the root.
- Max-heap: every parent is greater than or equal to its children. The largest element is always at the root.
Unlike a BST, there's no left-vs-right ordering rule — a node's left child and right child can be in either relative order, as long as both are on the correct side of the parent. That relaxation is exactly what makes heaps cheap to maintain.
In practice, a heap is stored as a flat array, not as linked nodes — the tree shape is implicit. For a node at index i: its children live at 2i + 1 and 2i + 2, and its parent lives at (i - 1) / 2. No pointers needed, which makes heaps cache-friendly and memory-light compared to a pointer-based tree.
A priority queue is the abstract interface ("give me the next-highest-priority item"); a heap is the concrete data structure almost everyone uses to implement it efficiently.
Swift's standard library has no built-in heap or priority queue — this is a genuinely common interview gap, and hand-rolling one (or knowing the shape of one cold) is frequently asked directly.
Reach for a heap when:
- You repeatedly need "give me the min/max, right now" — a classic priority queue use case (task scheduling, Dijkstra's algorithm, event simulation).
- You're solving a "top K" or "K-th largest/smallest" style problem — a heap gets you there in
O(n log k)instead of sorting everything inO(n log n). - You need a merge of many sorted sequences (merge K sorted lists) — a heap tracks "the smallest unmerged head" cheaply.
Skip it when you need the full sorted order, not just repeated access to one end — at that point you're paying heap overhead for something a single .sorted() call gives you more simply.
A min-heap, shown both as a tree (for intuition) and as the flat array that actually backs it:
┌────┐
│ 1 │ index 0 ← root, always the minimum
└────┘
/ \
┌────┐ ┌────┐
│ 3 │ │ 4 │ indices 1, 2
└────┘ └────┘
/ \ \
┌────┐ ┌────┐ ┌────┐
│ 6 │ │ 7 │ │ 8 │ indices 3, 4, 5
└────┘ └────┘ └────┘
Backing array: [ 1, 3, 4, 6, 7, 8 ]
Index: 0 1 2 3 4 5
parent(3) = (3-1)/2 = 1 → array[1] = 3 ✓ (3 ≤ 6, heap property holds)
children(1) = 2*1+1=3, 2*1+2=4 → array[3]=6, array[4]=7 (both ≥ 3 ✓)
Note: 6 and 7 are NOT ordered relative to each other — only relative
to their shared parent. A heap is not a sorted list.
No stdlib equivalent — array-backed, generic over any type, driven by a comparator closure so the same type works as a min-heap or max-heap.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first } // O(1) — the min (or max) is always the root
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
// New element starts at the last slot and "bubbles up" while it violates
// the heap property relative to its parent.
private mutating func siftUp(from index: Int) {
var child = index
var parent = parentIndex(of: child)
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = parentIndex(of: child)
}
}
// Root gets replaced by the last element, which then "sinks down" while
// it violates the heap property relative to its smaller (or larger) child.
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = leftChildIndex(of: parent)
let right = rightChildIndex(of: parent)
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return } // heap property restored
elements.swapAt(parent, candidate)
parent = candidate
}
}
private func parentIndex(of index: Int) -> Int { (index - 1) / 2 }
private func leftChildIndex(of index: Int) -> Int { 2 * index + 1 }
private func rightChildIndex(of index: Int) -> Int { 2 * index + 2 }
}Usage — the sort closure is what flips this between a min-heap and a max-heap:
var minHeap = Heap<Int>(sort: <) // smallest element always at the root
[8, 3, 10, 1, 6, 14, 4, 7].forEach { minHeap.insert($0) }
minHeap.extract() // 1
minHeap.extract() // 3
var maxHeap = Heap<Int>(sort: >) // largest element always at the root
[8, 3, 10].forEach { maxHeap.insert($0) }
maxHeap.peek // 10| Operation | Big-O | Why |
|---|---|---|
| Peek (min/max) | O(1) |
The root of a heap is always at index 0 — no search required. See Big-O Notation. |
| Insert | O(log n) |
Append to the end, O(1), then sift up at most height times — height of a heap is always log n because it's a complete binary tree (never skewed, unlike a plain BST). |
| Extract min/max | O(log n) |
Swap root with last element, remove last (O(1)), then sift down at most height times. |
Build a heap from n elements |
O(n) |
Surprising but true — repeatedly sifting down from the bottom up is O(n), not O(n log n), because most nodes are near the bottom and sift down only a short distance. Swift's Heap(sort:) above builds via repeated insert, which is O(n log n) — worth knowing the faster O(n) "heapify" exists even if you don't hand-roll it live. |
| Space | O(n) |
One array slot per element, no pointer overhead — this is why heaps beat pointer-based trees on memory. |
A heap is a triage nurse, not a sorted line — it only ever promises to hand you the single most urgent item instantly, and cheaply re-sorts itself just enough after every arrival or departure.
The peek property above returns elements.first, which is O(1). Why can a heap guarantee O(1) access to the minimum (or maximum) element, when a plain, unsorted array cannot guarantee better than O(n) for the same query — and why can't a heap give you the same O(1) guarantee for the second-smallest element?