Heaps and priority queues cheat sheet

Push values into a min-heap by hand

A heap stored in a list keeps each parent at index (i - 1) // 2 no larger than its children. A push appends at the end and swaps upward until the parent is not larger. Each push climbs at most the height of the tree, O(log n), so n pushes cost O(n log n), and the heap takes O(n) space. The result matches what heapq.heappush produces.

def push_all(values: list[int]) -> list[int]:
    heap: list[int] = []
    for v in values:
        heap.append(v)
        i = len(heap) - 1
        while i > 0:
            up = (i - 1) // 2  # parent slot
            if heap[up] <= heap[i]:
                break
            heap[up], heap[i] = heap[i], heap[up]
            i = up
    return heap

The k-th biggest reading

Keep a min-heap of the k largest values seen so far. Push each reading; when the heap grows past k, pop its smallest. At the end the heap's root holds the k-th largest. O(n log k) time and O(k) memory, and it works on a stream.

from heapq import heappop, heappush


def kth_largest(readings: list[int], k: int) -> int:
    keep: list[int] = []  # the k biggest so far; smallest on top
    for r in readings:
        heappush(keep, r)
        if len(keep) > k:
            heappop(keep)  # drop the smallest of k + 1
    return keep[0]

Merge many sorted feeds into one

Keep a min-heap holding the current front value of each feed, tagged with which feed and position it came from. Pop the smallest, output it, and push the next value from the same feed. With N values across k feeds, each value is pushed and popped once: O(N log k) time, O(k) heap memory.

The k depots nearest the warehouse

Squared distance x² + y² orders points the same way as real distance, with no square roots. Keep a max-heap of size k on (distance, x, y) by pushing negated keys; pop when it grows past k. Then sort the k survivors. O(n log k) time, O(k) memory.

from heapq import heappop, heappush


def nearest(depots: list[list[int]], k: int) -> list[list[int]]:
    worst_first: list[tuple[int, int, int]] = []  # negated keys
    for x, y in depots:
        heappush(worst_first, (-(x * x + y * y), -x, -y))
        if len(worst_first) > k:
            heappop(worst_first)  # the farthest of k + 1 goes
    best = sorted((-d, -x, -y) for d, x, y in worst_first)
    return [[x, y] for _, x, y in best]

Fewest time slots when each job type needs a cooldown

Greedy: in each round of gap + 1 slots, run the letters with the most jobs left, one each, using a max-heap of remaining counts. Idle slots fill a round only if more work remains. Each job is popped and pushed once per run: O(n log 26) = O(n), and the heap holds at most 26 counts: O(1) space. There is also a closed form: max(n, (most - 1) · (gap + 1) + letters tied for most).

Median after each new reading

Keep the smaller half in a max-heap and the larger half in a min-heap, with sizes equal or the low half one bigger. Each new value goes to the right half, then one value moves across if the sizes drift. The median is the low top, or the mean of both tops. O(log n) per reading, O(n log n) in total, and O(n) space for the heaps.

Smash the two heaviest rocks until one is left

A max-heap gives the two heaviest in O(log n) each. Push the difference back when it is non-zero. Each smash removes at least one rock, so there are at most n rounds: O(n log n) time, with O(n) space for the heap.

from heapq import heapify, heappop, heappush


def last_rock(rocks: list[int]) -> int:
    pile = [-w for w in rocks]  # max-heap by negation
    heapify(pile)
    while len(pile) > 1:
        heavy, next_heavy = -heappop(pile), -heappop(pile)
        if heavy > next_heavy:
            heappush(pile, next_heavy - heavy)
    return -pile[0] if pile else 0

Cheapest way to join ropes into one

Always join the two shortest ropes. Short ropes then take part in the most joins, which is what keeps the total low (the same argument as Huffman coding). A min-heap gives the two shortest in O(log n): O(n log n) total, with O(n) space for the heap.

from heapq import heapify, heappop, heappush


def join_cost(ropes: list[int]) -> int:
    pile = list(ropes)
    heapify(pile)
    total = 0
    while len(pile) > 1:
        joined = heappop(pile) + heappop(pile)  # the two shortest
        total += joined
        heappush(pile, joined)
    return total

How a binary heap works

A binary heap is a complete binary tree where every parent is no larger than its children (for a min-heap). It is stored in a plain list: children of i at 2i + 1 and 2i + 2. Peek is O(1), push and pop are O(log n), and building from a list with heapify is O(n). Searching for an arbitrary value is O(n).

Heap, sort or quickselect?

Sort when you need everything in order once: O(n log n), simple. Use a heap when items keep arriving or you only need the top k: O(n log k), and it works on streams. Use quickselect for one k-th value in a fixed in-memory list: O(n) on average but O(n²) worst case. Job schedulers use heaps because new jobs keep arriving and only the next one matters.