Heaps & Priority Queues

The problem a heap solves#

Suppose you constantly need to know "what's the smallest (or largest) item in this collection right now?" — while also constantly adding and removing items. Sorting the whole collection every time something changes would work, but it's wasteful: a full sort is O(n log n), and you'd be redoing most of that work over and over for a question that only cares about one extreme value. A heap answers "what's the smallest/largest item?" in O(1), and adds a new item or removes that extreme item in O(log n) — without ever fully sorting anything.

Analogy: think of a heap as a "leaderboard shortcut" rather than a fully sorted list. You don't need to know who's in 47th place — you only ever care who's currently in 1st. A heap keeps whoever is "most extreme" (smallest, or largest, depending on which kind you build) sitting right at the top, instantly reachable, while everyone else is only loosely organized — just organized enough to cheaply promote a new "1st place" the moment the current one is removed.

Min-heap vs max-heap#

A min-heap keeps the smallest value always accessible at the top (the root). A max-heap keeps the largest value at the top. Both are built on the same underlying rule, called the heap property:

For a min-heap: every parent node's value is less than or equal to both its children's values (and symmetrically, "greater than or equal to" for a max-heap).

Crucially, this is a weaker rule than a binary search tree's — a heap makes no promise about how left compares to right, or about any ordering between nodes that aren't in a direct parent-child relationship. It only guarantees the single strongest node sits at the root, recursively, all the way down. That relaxed rule is exactly what makes heap operations cheaper to maintain than a fully sorted structure.

Min-heap example:
        1
       / \
      3   2
     / \
    9   7

Every parent <= its children. The root (1) is guaranteed to be the smallest
value anywhere in the heap — but notice 3 and 2 aren't in sorted left-right
order, and neither are 9 and 7. That's fine — the heap property never promised that.

The array-based representation#

Here's the elegant trick that makes heaps fast and memory-efficient: despite being conceptually a tree, a binary heap is almost always stored as a plain array — no Node objects, no pointers at all. A parent-child relationship is captured purely through index arithmetic:

• The root lives at index 0.
• A node at index i has its left child at index 2i + 1 and its right child at index 2i + 2.
• A node at index i has its parent at index (i - 1) // 2.

# The min-heap drawn above, stored as a flat array:
heap = [1, 3, 2, 9, 7]

# heap[0] = 1  (root)
# heap[1] = 3  (heap[0]'s left child, since 2*0+1 = 1)
# heap[2] = 2  (heap[0]'s right child, since 2*0+2 = 2)
# heap[3] = 9  (heap[1]'s left child, since 2*1+1 = 3)
# heap[4] = 7  (heap[1]'s right child, since 2*1+2 = 4)

Because everything lives in one contiguous array, a heap gets all the cache-friendliness of arrays discussed earlier in this course, with none of the pointer overhead of a linked structure — this is a big part of why heaps are the standard choice for priority queues in practice.

Python's heapq module#

You will essentially never need to hand-roll a heap's insert/remove logic (which involves an operation called "sift up"/"sift down" to restore the heap property after a change) — Python's standard library already provides one, via the heapq module. heapq implements a min-heap directly on top of a plain Python list.

import heapq

tasks = []
heapq.heappush(tasks, 5)   # add an item, maintaining the heap property — O(log n)
heapq.heappush(tasks, 1)
heapq.heappush(tasks, 3)
heapq.heappush(tasks, 8)

print(tasks[0])             # 1 — the smallest item is always at index 0, O(1) to peek

print(heapq.heappop(tasks)) # 1 — removes and returns the smallest item, O(log n)
print(heapq.heappop(tasks)) # 3 — the next-smallest has bubbled up to the top

Since heapq only implements a min-heap, a common trick for a max-heap is to negate values on the way in and out:

max_heap = []
for value in [5, 1, 3, 8]:
    heapq.heappush(max_heap, -value)   # store the negation

print(-max_heap[0])          # 8 — the "largest" original value, recovered by negating back
print(-heapq.heappop(max_heap))  # 8

A priority queue is simply this same idea generalized: instead of comparing raw values, you compare items by an explicit "priority," typically by pushing (priority, item) tuples — heapq compares tuples element by element, so the priority (the first element) determines order:

priority_queue = []
heapq.heappush(priority_queue, (2, "write report"))
heapq.heappush(priority_queue, (1, "fix critical bug"))
heapq.heappush(priority_queue, (3, "reply to email"))

while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"{priority}: {task}")

# 1: fix critical bug
# 2: write report
# 3: reply to email

This is precisely how real task schedulers, pathfinding algorithms (Dijkstra's algorithm, covered in the algorithms course, leans on exactly this structure), and event simulations decide "what should happen next" — always pull whatever currently has the highest priority (lowest number, in this convention), in O(log n).

Classic use case: finding the k largest (or smallest) elements#

A frequent real-world need: out of a huge collection, find just the top k — the 10 highest exam scores, the 5 slowest API requests, the 3 cheapest flights. Sorting the entire collection just to read off the first or last k values is wasteful: that costs O(n log n) when you don't actually care about the order of the other n - k elements at all.

A heap solves this in O(n log k) — dramatically better than a full sort when k is much smaller than n. The idea: maintain a min-heap of size k. Walk through every element; if the heap isn't full yet, add it. Once it's full, compare each new element to the heap's smallest member (the root) — if the new element is bigger, it deserves a spot in the "top k" more than the current smallest does, so swap them.

import heapq

def k_largest(nums, k):
    heap = []

    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)               # still filling up the heap
        elif num > heap[0]:                          # bigger than our current smallest "top k" member
            heapq.heapreplace(heap, num)              # pop the smallest, push the new one — one O(log k) step

    return sorted(heap, reverse=True)


print(k_largest([3, 1, 5, 12, 2, 11, 9], 3))   # [12, 11, 9] — the 3 largest values

Conveniently, heapq also provides this directly as a one-liner for common cases, built on the same underlying idea:

import heapq

print(heapq.nlargest(3, [3, 1, 5, 12, 2, 11, 9]))    # [12, 11, 9]
print(heapq.nsmallest(3, [3, 1, 5, 12, 2, 11, 9]))   # [1, 2, 3]

The key insight to remember: the heap here only ever holds k elements, no matter how large the input is — that's what caps the cost of each comparison/replacement at O(log k) instead of O(log n), and it's why this approach comfortably beats a full sort whenever you only need a small, fixed number of extremes out of a huge collection.

Common mistakes#

• Sorting the entire collection when you only need the top k. It works, but it's needlessly expensive — O(n log n) instead of O(n log k) — anytime k is small relative to n.
• Forgetting heapq is a min-heap only. Trying to use it directly for "largest first" without negating values (or using heapq.nlargest) gives you the smallest values instead.
• Assuming a heap is fully sorted. Only the root is guaranteed to be the min (or max) — heap[1] and heap[2] are not guaranteed to be in any particular order relative to each other; you must pop repeatedly to extract values in sorted order.
• Reaching for a heap when a hash table or simple sort would do. Heaps shine specifically for "repeatedly access the current min/max while the collection keeps changing" or "find the top k of many" — for a one-time, one-shot need to fully sort everything, sorted() is simpler and just as fast.