Heap — Always Know the Smallest

What is it? #

A heap keeps one item — the smallest, or the largest — instantly available, without keeping everything sorted.

That partial order is the trick. Maintaining full sorted order on every insertion costs more than you need if you only ever look at the extreme.

A min-heap guarantees the smallest is at the top. Inserting and removing are both O(log n); peeking at the top is O(1).

Python's heapq module implements a min-heap over a plain list. For a max-heap, push negated values.

Think of it like this #

A hospital emergency department. Patients are not sorted into a complete ranking from most to least urgent — that would be wasteful. What matters is that the most urgent case is always next. New arrivals slot in at the right level of priority, and the top of the list is always correct.

Simple example #

You process a million log entries and need the ten slowest requests. Sorting everything is O(n log n) and holds the whole dataset. A heap of size ten gives the same answer in one pass with almost no memory.

Code #

import heapq

# A min-heap is just a list maintained by heapq
heap = []
for value in [7, 2, 9, 1, 5]:
    heapq.heappush(heap, value)       # O(log n)

print(heap[0])                        # 1 — smallest, O(1) peek
print(heapq.heappop(heap))            # 1 — remove smallest, O(log n)
print(heapq.heappop(heap))            # 2


# Top-K without sorting everything: keep a heap of size k
def top_k_slowest(requests, k=3):
    heap = []                          # min-heap of the k largest seen
    for duration, path in requests:
        if len(heap) < k:
            heapq.heappush(heap, (duration, path))
        elif duration > heap[0][0]:
            heapq.heapreplace(heap, (duration, path))
    return sorted(heap, reverse=True)


requests = [(120, "/a"), (45, "/b"), (900, "/c"), (300, "/d"), (60, "/e")]
print(top_k_slowest(requests))        # [(900, '/c'), (300, '/d'), (120, '/a')]


# Priority queue for scheduling: lower number = higher priority
tasks = []
heapq.heappush(tasks, (2, "send weekly report"))
heapq.heappush(tasks, (0, "restart failed worker"))
heapq.heappush(tasks, (1, "clear cache"))

while tasks:
    priority, name = heapq.heappop(tasks)
    print(priority, name)             # 0, 1, 2 in order


# Max-heap by negating
max_heap = []
for value in [7, 2, 9]:
    heapq.heappush(max_heap, -value)
print(-heapq.heappop(max_heap))       # 9


# Merging sorted streams lazily
print(list(heapq.merge([1, 4, 9], [2, 5], [3, 8])))   # [1, 2, 3, 4, 5, 8, 9]

Finding the top 10 of 1,000,000 items

sort everything      O(n log n)   holds 1,000,000 items
heap of size 10      O(n log 10)  holds 10 items

How it works #

A heap is conceptually a binary tree where every parent is smaller than its children, stored compactly in an array. The smallest is always at index 0.

heappush places the new item at the end and moves it upwards while it is smaller than its parent. That bubbling takes at most log n steps because the tree height is log n.

heappop takes the top, moves the last item to the root and pushes it down until order is restored — again log n steps.

There is no full ordering. Printing the underlying list shows something that looks unsorted, and that is correct: only the parent-child relationship is guaranteed.

top_k_slowest keeps a min-heap of exactly k items. The smallest of the current top-k sits at index 0, so comparing each new duration with heap[0] decides in one step whether it belongs. heapreplace pops and pushes in a single operation.

Tuples work naturally as heap items because Python compares them element by element, so (priority, name) sorts by priority first. Adding a counter as a tiebreaker — (priority, counter, task) — avoids comparing unorderable objects when priorities tie.

heapq.merge lazily merges already-sorted inputs, which is how external merge sort combines sorted files.

Real-world use #

Priority queues are used by task schedulers, operating systems, and job runners that must handle urgent work first. Dijkstra's shortest-path algorithm relies on one to always expand the nearest unvisited node.

Top-N problems are extremely common: slowest endpoints, biggest tables, most frequent errors, nearest locations. A heap answers all of them in one pass over data that may be far too large to sort.

Event simulations use a heap keyed by timestamp to always process the next event. Rate limiters and timers use the same idea.

Streaming is where heaps really shine. You can process an endless feed and always know the current top-k, which sorting simply cannot do.

Common mistakes #

• Assuming the heap list is fully sorted. Only the top is guaranteed.
• Sorting an entire dataset to get the top five instead of using a size-five heap.
• Forgetting Python only provides a min-heap; negate values for a max-heap.
• Pushing tuples whose later elements are not comparable, causing errors on ties — add a counter.
• Modifying an item already in the heap, which breaks the ordering invariant.

Practice #

Given a stream of (timestamp, event) tuples, write a function that returns the five most recent events using a heap of fixed size. Then implement a task scheduler that pops tasks by priority and, for equal priorities, by insertion order.