Heaps & Priority Queues

When I built the task scheduler for my Python orchestration framework, I kept running into a specific problem: I needed to repeatedly pull the highest-priority job from a queue that was constantly receiving new entries. My first attempt sorted the entire queue on each insertion — and on a realistic load of a few hundred concurrent tasks, the scheduler spent more CPU time resorting the list than actually running jobs.

The correct tool is a heap. A heap gives you the minimum (or maximum) element in O(1) and accepts new elements in O(log N) — without ever sorting the full collection. Once I replaced the sort with heapq, the scheduler overhead dropped to noise.

The three patterns that cover nearly every heap problem are:

• Top-K: keep a size-K min-heap while streaming N elements — O(N log K)
• Merge-K sorted lists: use a heap to pick the globally smallest item across K iterators — O(N log K)
• Running median: maintain a max-heap of the lower half and a min-heap of the upper half — O(log N) per insert, O(1) read

A heap is a complete binary tree with one invariant: every parent is smaller than or equal to both its children. That single rule is what makes the minimum always available at the root in O(1).

Think of it like a tournament bracket played in reverse: the winner (smallest) sits at the top, and every match below it only needs to satisfy the local parent-child relationship, not a total order across all nodes. That is why heapify runs in O(N) while sorting the same data takes O(N log N) — you only fix local violations, not global order.

Python's heapq module implements a min-heap over a plain list. You never build the tree structure yourself — the list IS the tree, with element at index i having children at 2i+1 and 2i+2.

graph TD
  A["1 (root — minimum)"]
  B["3"]
  C["2"]
  D["4"]
  E["5"]
  F["9"]
  G["6"]
  A --> B
  A --> C
  B --> D
  B --> E
  C --> F
  C --> G
  style A fill:#4ade80,stroke:#16a34a

The green root is always the minimum. Every edge points from parent to child, and the parent is always smaller. This is the heap invariant. Notice that siblings (B and C, or D and E) have no required relationship — there is no global left-to-right order, only the local parent-child rule.

The goal: find the K largest (or smallest) elements from a stream of N, using O(K) space.

The trick: a min-heap of size K. Push each element; when the heap exceeds K, pop the minimum. After N elements, the heap contains the K largest.

Why a min-heap for the K largest? Because you want to evict the smallest element when the heap overflows — and the min-heap always puts the smallest at the root. Pop it, and you are left with the K largest seen so far.

Pattern 2: Merge K Sorted Lists

You have K sorted lists (from K database shards, K log files, K API pages) and need to merge them into one sorted stream. The naive approach — concatenate and sort — is O(N log N). The heap approach is O(N log K), which matters when K is small and N is large.

The heap always holds at most K elements — one per list. Every pop produces the next element of the merged output, and every push advances one list's pointer.

Pattern 3: Running Median

Maintain a running median as numbers stream in. The two-heap split is the classic approach: a max-heap holds the lower half of seen values, a min-heap holds the upper half. The invariant: the max-heap may be at most one element larger.

Close the code and try these from memory:

1. You want the 5 most expensive log events from a stream of a million. Which heap type do you use, and what do you do when the heap grows beyond 5?
2. Why is heapify faster than N heappush calls on the same data?
3. In merge-K sorted lists, what does each element in the heap represent?
4. In the running-median two-heap pattern, what does it mean when the max-heap top is larger than the min-heap top?

Problem: Given an integer array nums and an integer k, return the kth largest element in the array. You must solve it in O(N log K) time — do not sort the full array.