Core pattern

Heap: hospital triage: most urgent first

Learn the heap pattern through one picture you won’t forget, worked on Min-heap push and pop.

The example problem

Keep a collection where you can always add a value and take out the smallest value quickly (a min-heap / priority queue).

Input:  patients arrive with severities 5, 3, 8, 1, 6
Output: they are treated in order 1, 3, 5, 6, 8

Picture it

Picture hospital triage: the most urgent patient (smallest number) must always be seen first. The heap is a tree where every parent is more urgent than its children, so the most urgent is at the top. A new patient joins at the bottom and bubbles up past less urgent parents. When the top patient leaves, the last one moves to the top and sinks down.

The key idea

A heap keeps only partial order (parent ≤ children), stored as a list. Push and pop are O(log n).

Python

def push(heap, x):
    heap.append(x)
    i = len(heap) - 1
    while i > 0 and heap[(i - 1) // 2] > heap[i]:
        p = (i - 1) // 2
        heap[i], heap[p] = heap[p], heap[i]
        i = p

def pop(heap):
    top = heap[0]
    heap[0] = heap.pop()        # last patient to the top
    sift_down(heap, 0)          # let them sink
    return top

Practise heap

NeetCode 150 problems that use it

Heap / Priority Queue ·