data structures~14 minRoute 02 8 of 9

Heaps & Priority Queues

Always-the-smallest (or largest) at the top — log-time inserts and pops.

Story — the ER triage nurse

An ER nurse looks at the patients in the waiting room. Not at all of them — at the chart on top. Whoever is sickest goes next. After they head in, the nurse glances down, picks the next worst, hands them up. The pile is loose-sorted by urgency, but only the most urgent at any moment is at the top.

That is a heap. Specifically a priority queue — a queue where the next item out is the most-important, not the oldest. The heap implementation promises one thing: the smallest (or largest) value is always at the root. Everything else is loosely ordered.

Heapa says

A heap is almost always stored as a flat array, not a tree of pointers. Parent of i is (i - 1) / 2, children are 2i+1 and 2i+2. No allocations, great cache behaviour.

See it — push bubbles up, pop sifts down

Push a value: it lands at the end, then bubbles up while smaller than its parent. Pop: take the root, move the last leaf into its place, then sift down (swap with the smaller child) until the heap property holds again. Both are O(log n).

A min-heap of 7 values. Root is the smallest.

stored as: [3, 7, 5, 12, 9, 8, 15]

Push

Heapa says

A min-heap promises only one thing: the root is the smallest. Everything else can be in any order — that's why insert and pop are fast.

Try it — when does a heap beat sorted-array?

Exercise. You're writing a job scheduler. Jobs arrive constantly with priorities. You always need to grab the highest priority next. Heap or sorted array?

Reveal answer

Heap. Insert is O(log n) for a heap, O(n) for a sorted array (shift). Extract-max is O(log n) for the heap, O(1) for the array. Heap wins on insert by a factor of n; loses on extract by a constant. Net win for any non-trivial scale.

Code it — five languages

Python, Java, C++ ship one out of the box. JavaScript and Go make you build it (or pull a tiny library). All implementations share the same shape under the hood.

import heapq

# Python's heapq is a min-heap operating on a plain list.
h = []
heapq.heappush(h, 7)
heapq.heappush(h, 3)
heapq.heappush(h, 5)

print(heapq.heappop(h))    # 3 — smallest
print(heapq.heappop(h))    # 5
print(h)                    # [7]

Quiz it — make it stick

Question 1
A min-heap guarantees only one thing about the structure. What is it?
The whole array is sortedThe smallest value is always at the rootEach level is fuller than the one below itNo two values are equal
True or false — Question 2
A heap and a binary search tree are the same data structure with different names.

Predict — Question 3

You push 5, 3, 7, 1 onto an empty min-heap (in that order), then pop twice. What did you get out?

# Visualize after each push:
# push 5 → [5]
# push 3 → [3, 5]
# push 7 → [3, 5, 7]
# push 1 → [1, 3, 7, 5]
# pop  → 1, then heap reorders
# pop  → 3

Your guess

No Dumb Questions

Real questions other learners asked on this page.

What's a priority queue?
A queue where the next item out isn't the oldest, but the most-important. Heaps are the canonical implementation: insert and extract-min both run in O(log n). Used in Dijkstra's algorithm, A* search, scheduling.
Min-heap or max-heap?
Min-heap pops the smallest; max-heap pops the largest. They're mirror images. Choose based on what "highest priority" means in your problem.
How do I find the kth smallest element with a heap?
Maintain a max-heap of size k while scanning; for each new element, push it and pop if size exceeds k. The heap's root at the end is the kth smallest. Beats sorting when k is much smaller than n.