Heaps and priority queues

A queue processes items in arrival order. A priority queue processes them in importance order — and a heap is the data structure that makes "give me the most important item" fast, without keeping everything fully sorted.

Intermediate

5 min read

The problem a heap solves

tasks = [("write report", 3), ("fix critical bug", 1), ("reply to email", 5)]
# Lower number = higher priority. Need: always process the lowest-priority-number task next.

A regular queue (from the stacks-and-queues lesson) processes items in the order they arrived — first in, first out, with no concept of "this one matters more." A priority queue processes items in order of priority instead: whatever's most important comes out next, regardless of when it was added. The naive approach — keep the list fully sorted at all times — makes "get the most important item" fast (O(1), it's just the front), but every insertion becomes O(n) to find the correct sorted position. A heap gets both operations fast at the same time, which is the entire reason it exists.

What a heap actually guarantees — weaker than fully sorted, on purpose

A min-heap guarantees exactly one thing: every parent node is less than or equal to both its children. That's it — it does not guarantee the whole thing is sorted; the tree above is a valid min-heap even though 3 and 2 aren't in sorted order relative to each other, and neither are 5, 4, and 2. This weaker guarantee is precisely what makes a heap fast: maintaining parent <= children after an insertion or removal only requires fixing up one path from root to leaf (or leaf to root) — O(log n) — rather than the O(n log n) cost of keeping an entire sequence fully sorted at all times.

How a heap is actually stored: an array, not a tree of nodes

# The heap pictured above, as a flat array:
heap = [1, 3, 2, 5, 4]
# heap[0] is the root
# for any index i: left child = heap[2*i + 1], right child = heap[2*i + 2], parent = heap[(i-1)//2]

Despite being described and drawn as a tree, a heap is normally implemented as a plain array — the parent/child relationships are computed from index arithmetic instead of storing explicit pointers, the same "index math instead of real links" idea behind how a hash table's buckets are addressed. This is significantly more memory-efficient than an actual linked tree structure (from the trees lesson) with real node objects and child pointers, and it's exactly what Python's heapq module does internally — a heap is just a list, manipulated with specific rules.

Using Python's built-in heap: `heapq`

import heapq
 
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
 
heapq.heappop(heap)   # 1 — always removes and returns the smallest
heapq.heappop(heap)   # 3
heap[0]                # 5 — peek at the smallest without removing it (heap[0] is always the min)

heapq implements only a min-heap directly — heappop always returns the smallest item, both heappush and heappop run in O(log n), and heap[0] is always the current minimum without needing to remove anything. There's no separate "heap" type; heapq's functions operate on a plain Python list, maintaining the heap property as a side effect of using heappush/heappop instead of plain list operations.

Getting a max-heap out of a min-heap-only library

import heapq
 
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)
 
-heapq.heappop(max_heap)   # 5 — negate on the way in, negate again on the way out

Since heapq only provides a min-heap, the standard trick for a max-heap (when the largest item is what's needed next) is negating every value going in and negating it again coming out — the smallest negated value corresponds to the largest original value. This is a real, commonly used pattern, not a hack to be embarrassed about; it's simpler than reimplementing a whole separate max-heap.

The actual use case: priority-based task processing

import heapq
 
tasks = []
heapq.heappush(tasks, (1, "fix critical bug"))
heapq.heappush(tasks, (3, "write report"))
heapq.heappush(tasks, (5, "reply to email"))
 
priority, task = heapq.heappop(tasks)
print(task)   # "fix critical bug" — heapq compares tuples element-by-element, so priority (first) decides order

Pushing (priority, item) tuples works because Python compares tuples lexicographically — first by the first element, which is exactly what's wanted here: the priority number decides order, and heapq handles everything else. This tuple-based pattern is the standard way to build a real priority queue on top of heapq, and it's exactly what a task scheduler, an event simulation queue, or a "process the closest unvisited node next" algorithm (Dijkstra's shortest path, which is a direct extension of BFS using a priority queue instead of a plain queue) all rely on underneath.

Why not just use `sorted()` every time?

tasks.append(new_task)
tasks.sort()          # O(n log n) — re-sorts everything, every single insertion
next_task = tasks.pop(0)   # O(n) too — removing from the front of a list shifts everything

Re-sorting the entire list on every insertion is correct but wasteful — a heap gets the same "always know the next most important item" behavior for O(log n) per insertion and removal, instead of paying O(n log n) (sort) or O(n) (shift) every single time. The heap's weaker guarantee — not fully sorted, just parent <= children — is exactly what buys back that speed, the same kind of trade the hash-map-pattern lesson makes elsewhere: give up a stronger guarantee you don't actually need, in exchange for real speed.