Heaps, Tries & Advanced Patterns

01Heaps / priority queues

The problem: cheap repeated access to the extreme

You have a stream of items and repeatedly want the smallest (or largest). Options:

The structure

A min-heap is a complete binary tree (every level full, last level packed left) with one rule — the heap property: every parent ≤ its children. Nothing about siblings, nothing about global order. Just: the root is the minimum.

Completeness buys the killer implementation detail: store it in a plain array, no pointers.

        [1]                     array: [1, 3, 2, 7, 4, 5]
       /   \                            0  1  2  3  4  5
     [3]    [2]
     / \    /                   children of i:  2i+1, 2i+2
   [7] [4] [5]                  parent of i:    (i-1) // 2

Insert (sift up): append at the end (keeps completeness), then swap upward while smaller than the parent — O(height) = O(log n).

Extract-min (sift down): take the root; move the last element to the root (completeness again); swap downward with the smaller child while violating — O(log n).

extract-min:  [1] leaves → last elem [5] jumps to root → sifts down
        [5]                [2]
       /   \      ──►     /   \
     [3]    [2]         [3]   [5]

Heapify: building a heap in O(n), not O(n log n)

Pushing n items one by one is O(n log n). Heapify is smarter: start from the last non-leaf node and sift down, walking backwards to the root. Why it's O(n): half the nodes are leaves (sift distance 0), a quarter sift ≤ 1, an eighth sift ≤ 2… the sum Σ n/2^k · k converges to ~2n. Most nodes are near the bottom with nowhere to go — that's the whole trick, and it's why heapq.heapify(list) is O(n).

Python heapq — the working API

import heapq

h = [5, 1, 4]
heapq.heapify(h)              # O(n), in place; h[0] is now the min
heapq.heappush(h, 2)          # O(log n)
smallest = heapq.heappop(h)   # O(log n)
peek = h[0]                   # O(1) — just index, don't pop

heapq.nsmallest(3, data, key=len)   # convenience top-K
heapq.heappushpop(h, x)             # push then pop — one sift, ideal for top-K loops

02Heap patterns: Top-K, two heaps, k-way merge

Top-K — and the counterintuitive heap choice

"K largest elements from n items (or a stream)." Sorting is O(n log n) and needs all data in memory. The heap way: keep a MIN-heap of size k — yes, min — for the k largest.

def top_k(nums, k):
    h = nums[:k]
    heapq.heapify(h)
    for x in nums[k:]:
        if x > h[0]:
            heapq.heapreplace(h, x)     # evict the weakest, admit x
    return h                            # the k largest, O(n log k) time, O(k) space

O(n log k) beats O(n log n) when k ≪ n, and it streams — you never hold more than k items. That's "top 10 endpoints by error rate over a firehose of events" — a streaming top-K, which is why interviewers love it.

Family members: Kth Largest Element, K Closest Points (key = distance), Top K Frequent (Counter → heap on counts), Kth Largest in a Stream (persist the size-k heap between calls).

Two heaps (Find Median from Data Stream)

Median = the boundary between the lower half and upper half. So maintain both halves: a max-heap of the lower half and a min-heap of the upper half, sizes balanced within 1. Median = a root (or the mean of both roots). Insert O(log n), median O(1). This "straddle a boundary with opposing heaps" idea generalizes — IQR tracking, sliding-window medians.

K-way merge

Merge k sorted lists (Merge K Sorted Lists, Smallest Range Covering K Lists): heap of size k holding each list's current head; pop the global min, push that list's next element. O(N log k) for N total elements. This is literally how LSM-tree compaction (RocksDB/Cassandra) and external merge sort work — say so.

03Tries (prefix trees)

The problem: hashmaps can't do prefixes

A hashmap answers "is cat a key?" in O(1) — but "list every key starting with ca" requires scanning all keys, because hashing deliberately scatters similar keys apart. When the query is prefix-shaped — autocomplete, typeahead, spell-check, IP longest-prefix routing — you want similar keys stored together.

A trie stores strings as paths from the root, one character per edge, so all words sharing a prefix share a path. The prefix ca is a place in the tree; everything below it is exactly the set of completions.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}       # char → TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):                       # exact word
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):                # any word with this prefix?
        return self._walk(prefix) is not None

Trade-off: memory. A node per character plus a dict per node is heavy; production systems compress (radix trees — merge single-child chains — as in Linux routing tables and some router FIBs; DAWGs; or just sorted arrays + binary search when data is static).

Interview appearances: Implement Trie (above, verbatim), Design Add-and-Search Word (. wildcard ⇒ DFS branching over all children at that node), Word Search II (trie of the dictionary guides the grid backtracking — prune the moment the path isn't a prefix of anything), Longest Common Prefix.

04Pattern: intervals

Interval problems (meetings, bookings, on-call schedules, IP ranges, maintenance windows) all yield to one opening move: sort by start time. After sorting, only adjacent relationships matter, and everything becomes a single sweep.

The overlap test — two intervals overlap iff each starts before the other ends:

a: ├──────┤             overlap(a, b) ⇔ a.start < b.end and b.start < a.end
b:     ├──────┤          (after sorting by start, just: b.start < a.end)

Merge Intervals — the canonical one:

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:            # overlaps the last merged one
            out[-1][1] = max(out[-1][1], end)      # extend (careful: max, not end!)
        else:
            out.append([start, end])
    return out

Meeting Rooms II ("minimum rooms needed") — the interval/heap crossover: sort by start; min-heap of end times = rooms in use; for each meeting, if the earliest-ending room is free (heap[0] <= start), reuse it (pop), always push your end; answer = max heap size. Equivalently: sweep +1/−1 events and track the running maximum — max concurrency. That's the same computation as "peak concurrent connections" from access logs — say so.

Family: Insert Interval, Non-overlapping Intervals (min removals ⇒ greedy: sort by end, keep earliest-ending), Employee Free Time.

05Pattern: binary search on the answer

The most disguised pattern in interviews. Binary search doesn't need an array — it needs a monotonic yes/no question (full treatment of the template in file 08).

Recognition: the problem asks to "minimize the maximum" or "maximize the minimum" of something — and checking whether a given candidate value works is easy.

The reframe: instead of computing the answer directly, ask "could the answer be ≤ x?" If feasibility is monotone (works for x ⇒ works for all larger x), binary search x over its range, paying one O(n) feasibility check per probe.

Koko Eating Bananas (min speed to finish piles in h hours):

import math

def min_eating_speed(piles, h):
    def feasible(k):                       # can speed k finish in time?
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                       # mid works → try slower
        else:
            lo = mid + 1                   # too slow → must speed up
    return lo                              # smallest feasible speed

speed:     1   2   3   4   5   6   7   8
feasible:  N   N   N   Y   Y   Y   Y   Y
                       ▲
             binary search finds the N→Y boundary

O(n log(max_pile)). Family: Split Array Largest Sum / Capacity to Ship Packages in D Days (check: greedily pack under limit x, count chunks), Minimum Days to Make Bouquets, Aggressive Cows / Magnetic Force (maximize-the-minimum flavor — flip the branches).

06Choosing your tool — quick table

07Common interview questions

08Self-test