Heaps & Intervals

Heap = priority queue

A binary heap gives O(log n) push/pop and O(1) peek of the min (or max). Reach for it whenever you repeatedly need the current extreme of a changing set.

Top-K with a size-K heap

To find the K largest, keep a min-heap of size K: push each element, and if the heap exceeds K, pop the smallest. What remains is the top K.

import heapq

def k_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)     # drop the smallest so far
    return h                      # the k largest (unordered)
# Time O(n log k), Space O(k) — beats sorting's O(n log n) when k << n

Other heap classics

• Merge K sorted lists — push the head of each list; pop the min, push its successor. O(N log K).
• Streaming median — a max-heap of the lower half + a min-heap of the upper half, kept balanced; median is the top(s). O(log n) per insert.

Watch it run

The same heap shown both ways at once: the flat array that's actually in memory, and the complete binary tree it encodes. Watch values sift up on push and sift down after extract-min.

Intervals = sort first, then sweep

Watch the sweep in action — after sorting by start, every new interval either overlaps the block being built (stretch it) or starts a fresh one (gap). One pass, no backtracking:

Almost every interval problem starts by sorting by start (or end), then making one pass.

# Merge overlapping intervals.
def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= out[-1][1]:           # overlaps the last merged interval
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out
# Time O(n log n) for the sort, then O(n)

For "max concurrent intervals" (meeting rooms), sweep the sorted start/end events or use a min-heap of end times. Sort by end time for greedy "max non-overlapping intervals".

Practice — climb the ladder

Heap trigger words: "k largest", "k closest", "median of a stream". Interval trigger: sort by start (merge) or by end (scheduling), then sweep.