Lesson 9 of 16 Trees and Heaps

Heap Pattern: Top K, Merge K, Median

Heap and priority queue patterns: k largest elements with a size-k min-heap, merging k sorted lists, and a running median with two heaps in Python.

35-45 min intermediate 0/16 lessons done
Course contents Lesson 9 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. Python’s heapq in one minute
  4. Code
  5. Heap vs sorting vs quickselect
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • Why a min-heap of size k finds the k largest items.
  • Merging k sorted sequences with a heap of “next candidates”.
  • The two-heap running median.

Signals

  • “K largest / smallest / most frequent / closest”.
  • “Merge k sorted lists or arrays”, “next smallest across many sources”.
  • “Median of a stream”, scheduling by earliest deadline or end time.

Python’s heapq in one minute

heapq is a min-heap on a plain list: heappush and heappop are O(log n), heap[0] is the smallest. For a max-heap, push negated values. Tuples compare element by element, so (priority, tiebreaker, item) is the usual entry shape.

Code

"""Heaps: top-k, merge k sorted lists, running median."""
import heapq


def k_largest(nums, k):
    heap = []  # min-heap of the k largest seen so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)  # drop the smallest of the k+1
    return sorted(heap, reverse=True)


def merge_sorted(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out


class RunningMedian:
    def __init__(self):
        self.low = []   # max-heap (negated) of the smaller half
        self.high = []  # min-heap of the larger half

    def add(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))  # move the largest low to high
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2


if __name__ == "__main__":
    print(k_largest([3, 2, 1, 5, 6, 4], 2))
    print(merge_sorted([[1, 4, 5], [1, 3, 4], [2, 6]]))
    rm = RunningMedian()
    medians = []
    for x in [5, 15, 1, 3, 8]:
        rm.add(x)
        medians.append(rm.median())
    print(medians)

Output:

[6, 5]
[1, 1, 2, 3, 4, 4, 5, 6]
[5, 10.0, 5, 4.0, 5]
  • k largest: keep a min-heap of at most k items; when it grows to k+1, pop the smallest. What remains are the k largest. O(n log k) time, O(k) space; better than sorting when k ≪ n.
  • Merge k sorted lists: the heap holds one “next” element per list. Pop the smallest, push its successor. O(N log k) for N total elements. The list index i breaks ties so Python never compares incomparable items.
  • Running median: low is a max-heap of the smaller half, high a min-heap of the larger half. Each add routes through low to high and rebalances so low has the same size or one more. The median is low’s top or the average of both tops.

Heap vs sorting vs quickselect

NeedBest tool
Top k once, k smallSize-k heap, O(n log k)
Top k once, average O(n)Quickselect (worst case O(n²))
Top k as data streams inHeap
Everything in orderSort

Practise: heap / priority queue problems. Heaps also power Dijkstra’s algorithm and meeting rooms.

Key takeaways

  • Size-k min-heap → k largest; size-k max-heap → k smallest.
  • Merge k sorted sources with one candidate per source in a heap.
  • Two heaps keep a running median with O(log n) adds and O(1) reads.
  • Add a tiebreaker to heap tuples when items themselves aren’t comparable.

Exercises

  1. K closest points to the origin using a size-k max-heap.
  2. Reorganise a string so no two adjacent characters are equal (max-heap by count).
  3. Find the k-th largest element with quickselect and compare timings with the heap on 10⁶ numbers.

Quiz

  1. Why use a min-heap to find the k largest elements?
  2. What’s the complexity of merging k lists with N total elements?
  3. In the running median, what size invariant do the heaps keep?
Show answers
  1. Its top is the smallest of the current top-k, which is exactly the one to evict when a bigger element arrives.
  2. O(N log k): each element is pushed and popped once on a heap of at most k entries.
  3. low has either the same number of elements as high or exactly one more.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).