Heaps — Top K and running stats

Two patterns cover most: Top K = min-heap of size K, and running median = two heaps (max-heap for lower half, min-heap for upper).

The vocabulary, defined once

Heaps come with a cluster of words that all describe the same small idea from different angles. Here is every term you need, defined inline so you never have to look elsewhere:

• Heap — a tree-shaped collection that keeps its most-extreme element at the top (the root), so you can read or remove that one element cheaply. It is not fully sorted; only the top is guaranteed.
• Priority queue — the abstract idea a heap implements: a queue where items leave in priority order rather than arrival order. "Heap" is the usual concrete machinery; "priority queue" is the job it does. People use the two words interchangeably in interviews.
• Min-heap / max-heap — a min-heap keeps the smallest value at the root; a max-heap keeps the largest. Python's heapq is always a min-heap. That single fact drives most of the tricks below.
• Heap property — the one invariant the structure maintains: every parent is ≤ its children (min-heap) or ≥ its children (max-heap). Siblings have no required order — that freedom is what makes operations cheap.
• Complete binary tree — the shape a heap takes: every level is completely filled except possibly the last, which fills left-to-right. This tidy shape is why a heap can live inside a plain array (more on that below) and why its height is always about log n.
• peek — look at the root without removing it. Cost: O(1) — constant time, just read index 0.
• push (a.k.a. insert) — add an item. It lands at the bottom, then "bubbles up" past any parent it violates the heap property against. Cost: O(log n).
• pop (a.k.a. extract-min / extract-max) — remove the root and return it. The last item moves to the root, then "sinks down" until the heap property holds again. Cost: O(log n).
• heapify — turn an existing unordered array into a valid heap in one batch pass. Surprisingly, this is O(n), cheaper than pushing n items one at a time (which would be O(n log n)).
• O(log n) insert / extract — "log n" means: each push or pop only has to travel the height of the tree, and a complete binary tree of n items is only about log₂(n) levels tall. So even a million items is ~20 levels — each operation is roughly 20 comparisons, not a million.
• k-largest pattern — the recurring technique: to keep the K biggest items from a stream, maintain a min-heap capped at size K, evicting the smallest whenever it overflows. The root is then the K-th largest. (The mirror image — K smallest via a max-heap of size K — works the same way.)

A heap is just an array (the index trick)

You will hear "heap" and "tree" together, but in practice a heap is stored as a flat array — no node objects, no pointers. The complete-binary-tree shape lets simple arithmetic stand in for child/parent links. For an item at index i (0-based):

Traced: building a heap, then push and pop

The nightclub trace above showed the capped Top-K heap. Here we trace a plain min-heap with no size cap, so you can see the bubble-up and sink-down machinery directly. We'll insert 5, 3, 8, 1 one at a time, then pop twice. Each step shows the array (the real storage) and the tree it represents (parent above its children).

array: [5]      tree:  5

array: [3, 5]   tree:   3
                        /
                       5

array: [3, 5, 8]   tree:   3
                          / \
                         5   8

array: [1, 3, 8, 5]   tree:     1
                             / \
                            3   8
                           /
                          5

popped: 1
array: [3, 5, 8]   tree:   3
                          / \
                         5   8

popped: 3
array: [5, 8]   tree:   5
                       /
                      8

Notice the pattern: push drops an item at the end and bubbles it up toward the root; pop hands you the root, then moves the last item to the top and sinks it down. Each path is at most the tree's height (~log n), so both are O(log n). Popping repeatedly hands the items back in sorted order — that's exactly heap sort, and why pushing n items then popping all n is O(n log n).

Why "K-th largest = min-heap of size K" (the reasoning)

This is the single most counter-intuitive idea in the lesson, so here is the argument spelled out rather than asserted. You want the K-th largest value, yet you reach for a min-heap and keep throwing away small values. Why does that land on the right answer?

• Maintain a min-heap that never holds more than K items. Whenever a push makes it K+1, pop the smallest. So at every moment the heap contains exactly the K largest values seen so far — nothing smaller could have survived, because the smallest is always the first to be evicted.
• Within those K survivors, the smallest one is the K-th largest overall (the 1st-largest, 2nd-largest, … down to the K-th-largest, and the K-th is the floor of the group).
• In a min-heap the smallest item is the root, at index 0. So heap[0] is the K-th largest — no scan, no sort, read it in O(1).

The mental shortcut: the min-heap acts as a "doorman for the elite K." It only cares about keeping out anything that isn't in the top K, and the cheapest way to do that is to always know — and be ready to evict — the weakest current member. That weakest member is precisely your answer. The cost is O(n log K), far cheaper than sorting all n values (O(n log n)) when K is small, and the memory is only K, which matters for a never-ending stream.

The max-heap-via-negation trick

Python's heapq only builds min-heaps. When you need a max-heap — say you want to pop the largest item repeatedly — the standard workaround is to negate. Push -x instead of x, and negate again when you pop. Negation flips the ordering: the most-negative number is the smallest, so the min-heap surfaces what was originally the largest.

import heapq

nums = [5, 3, 8, 1]
h = []
for x in nums:
    heapq.heappush(h, -x)        # store the NEGATIVE

largest = -heapq.heappop(h)     # pop min of negatives = max of originals -> 8
next_largest = -heapq.heappop(h) # -> 5

The mental model: a min-heap on -x behaves like a max-heap on x, because the ordering is mirrored. The only discipline is to remember to flip the sign on the way out as well as in. (For tuples or objects where negation makes no sense, you instead push a (-priority, item) pair, or in some languages pass a custom comparator. Python also offers heapq.nlargest(k, data) as a one-shot convenience, but the negation trick is what you reach for inside a running/streaming algorithm.)

Recognizing a heap problem

Heaps shine in a narrow but common situation: you repeatedly need the most-extreme item from a changing set, and you do not need everything fully sorted. Signals that should make you reach for a heap:

Common pitfalls

• Using a max-heap for K-th largest. The natural instinct ("largest → max-heap") is wrong here. K-th largest uses a min-heap of size K; K-th smallest uses a max-heap of size K. The heap holds the opposite extreme of what the question names.
• Forgetting to cap the heap. If you push every value and never pop on overflow, the heap grows to n and you've thrown away the whole memory/speed advantage. The size guard (if len(h) > k: heappop(h)) is the algorithm.
• Forgetting to un-negate. With the max-heap trick, return -heappop(h), not heappop(h). A single missed sign flip silently returns negatives.
• Treating a heap as sorted. Only the root is ordered. Iterating the underlying array gives you near-arbitrary order — never index into h[1], h[2] expecting the 2nd/3rd smallest.
• Heapifying when you could build cheaply. If you already hold the full array, call heapq.heapify(arr) (O(n)) instead of pushing items one-by-one (O(n log n)).
• Comparing un-comparable payloads. If two pushed items tie on priority and the payload itself isn't orderable, Python raises a TypeError. Push (priority, tiebreaker, item) tuples so ties resolve on a comparable field.
• No built-in heap in some languages. Python has heapq and Java has PriorityQueue, but JavaScript/TypeScript ship nothing — bring a library or hand-roll push/pop with the index arithmetic above.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.h = []
        for v in nums: self.add(v)

    def add(self, v):
        heapq.heappush(self.h, v)
        if len(self.h) > self.k:
            heapq.heappop(self.h)
        return self.h[0]   # kth largest = smallest of top-k

Return the k-th largest value — run it live: