Heap — Tech Epitome

Heap

Constant-time access to the extreme, logarithmic to change it.

Medium14 problems

How do I recognise this pattern?

Repeatedly needing the smallest or largest remaining item.
Merging several sorted sequences.
Scheduling by priority, or simulating events in time order.
A running median, using two heaps facing each other.
Dijkstra's algorithm, or any best-first search.

When it is the wrong tool

You need the k-th element once — quickselect averages O(n) and beats building a heap.
Full sorted order is required.
Arbitrary elements must be searched or removed; a heap only exposes its root.

What is it?

A binary heap keeps the smallest (or largest) element at the root while only partially ordering everything else. That weaker guarantee is exactly why insertion and removal cost O(log n) rather than O(n), and it is all you need when the question only ever asks for the current extreme.

The core idea

A heap is a partially ordered tree, not a sorted list. Only the root is guaranteed. Iterating the backing array will not give you sorted output, and that surprises people.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1import heapq2 3 4def merge_sorted_lists(lists):5    """A heap of one candidate per list: always pop the global smallest."""6    heap = []7    for list_index, values in enumerate(lists):8        if values:9            # Carrying the indices lets us refill from the list we drained.10            heapq.heappush(heap, (values[0], list_index, 0))11 12    result = []13    while heap:14        value, list_index, value_index = heapq.heappop(heap)15        result.append(value)16 17        nxt = value_index + 118        if nxt < len(lists[list_index]):19            heapq.heappush(heap, (lists[list_index][nxt], list_index, nxt))20 21    return result22 23 24class RunningMedian:25    """Two heaps facing each other: a max-heap below, a min-heap above."""26 27    def __init__(self):28        self.low = []    # max-heap, stored negated29        self.high = []   # min-heap30 31    def add(self, value):32        heapq.heappush(self.low, -value)33        # Keep every element in 'low' no greater than every element in 'high'.34        heapq.heappush(self.high, -heapq.heappop(self.low))35        if len(self.high) > len(self.low):36            heapq.heappush(self.low, -heapq.heappop(self.high))37 38    def median(self):39        if len(self.low) > len(self.high):40            return -self.low[0]41        return (-self.low[0] + self.high[0]) / 2

Common mistakes

Expecting the heap's underlying array to be sorted.
Forgetting to negate on both push and pop when simulating a max-heap with a min-heap.
Pushing tuples whose later fields are not comparable, which throws when the first fields tie.
Mutating an element's priority after insertion and expecting the heap to reorder.

Problems using Heap

Problem	Difficulty	Role
How Many Studios?#83	Medium	Related
Fewest Depot Stops#90	Hard	Primary
Curriculum Order#103	Medium	Related