Heaps

A binary heap is a complete binary tree, usually stored in a plain array, that maintains one invariant: every parent is smaller (in a min-heap) or larger (in a max-heap) than its children. That single invariant is enough to answer "what's the smallest (or largest) element right now?" in O(1) time (peek), while still supporting O(log n) push and O(log n) pop. Contrast that with a sorted array, where lookup of the extreme is also O(1) but insertion costs O(n) to keep things sorted, or an unsorted array, where insertion is O(1) but finding the extreme costs O(n). A heap is the sweet spot when you need repeated access to a running minimum or maximum while the collection keeps changing.

A heap used this way is usually called a priority queue: instead of first-in-first-out, elements come out in priority order. Python's heapq module implements only a min-heap on top of a list — heapq.heappush(h, x) and heapq.heappop(h) always surface the smallest item. To simulate a max-heap, negate the values on the way in and negate them again on the way out (or push tuples like (-priority, item)), since there's no separate max-heap type in the standard library.

Four problem shapes come up again and again:

1. Top-k / k-most-frequent. Instead of sorting the entire input (O(n log n)) to find the k largest or k most frequent items, keep a heap of size k and discard whatever doesn't belong, giving O(n log k) — much better than a full sort when k is small relative to n.
2. Merging k sorted sequences. If you have k sorted lists (or streams) and want one globally sorted output, a min-heap holding one "current head" element per list lets you always pop the global minimum next in O(log k) per element, instead of concatenating and re-sorting everything.
3. Running statistics over a stream. When numbers arrive one at a time and you need a live statistic like the median, a single heap isn't enough — the classic trick is two heaps: a max-heap for the smaller half of the numbers seen so far and a min-heap for the larger half, kept balanced in size. The median is then either the top of one heap or the average of both tops, computable in O(1) after an O(log n) insert.
4. Nearly-sorted / k-sorted data. If you're told every element is at most k positions from its final sorted position, you don't need a general sort — a min-heap of size k+1 slid across the array produces the fully sorted result in O(n log k).

A generic template for the "bounded heap" style (top-k, k-sorted) looks like this:

import heapq

def process(stream, k):
    heap = []
    for item in stream:
        heapq.heappush(heap, item)
        if len(heap) > k:
            heapq.heappop(heap)  # discard whatever the heap says is least useful
    return heap

Complexity. Each heappush/heappop is O(log n) for a heap of size n. Bounding the heap to size k (instead of letting it grow to size n) is what turns an O(n log n) approach into O(n log k) — a real win whenever k is much smaller than n. Building a heap from an existing list all at once via heapq.heapify is O(n), cheaper than pushing elements one at a time.

Common pitfalls. A frequent mistake is sizing the heap at n when only the k most extreme elements ever matter — this wastes both time and memory compared to capping it at k. Another is forgetting that heapq is min-heap only, and reaching for the wrong sign convention when a problem calls for a max-heap. Tie-breaking is a subtle one too: when two elements compare equal on the primary key (e.g. same frequency), the heap needs a secondary key (like lexicographic order) baked into the tuple you push, or ties will resolve arbitrarily and inconsistently. Finally, remember that a heap gives you fast access to one extreme at a time — if you need both the min and the max efficiently, you need two heaps (or a different structure entirely), not one heap queried two ways.

This subject walks through four problems that showcase these patterns: selecting the k most frequent strings with correct tie-breaking, merging k sorted linked lists with a min-heap, maintaining a running median over a stream with two heaps, and sorting a k-sorted (nearly sorted) array with a bounded min-heap.