Heaps, selection and streaming

Why it matters

Whenever you repeatedly need the smallest or largest item while items keep arriving, a heap is the natural structure: schedulers pick the next job, Dijkstra's algorithm picks the closest unsettled node, a merger picks the smallest head among k sorted runs, and monitoring code keeps the slowest requests. Interviews use heaps for selection and streaming problems, and the follow-up questions test whether you know the alternatives.

Core ideas

Structure. A binary heap is a complete binary tree stored in an array: with 0-based index i, the children are at 2i + 1 and 2i + 2 and the parent at (i − 1) // 2. The heap property (every parent is no larger than its children, for a min-heap) puts the minimum at the root. Insert appends and sifts up; extract moves the last element to the root and sifts down. Both are O(log n) because the height is ⌊log₂ n⌋; peeking is O(1).

Build in O(n). Sifting down every internal node, from the last one back to the root, costs O(n) rather than O(n log n): most nodes sit near the bottom and move only a short distance, and the heights of all nodes in a complete tree sum to O(n). Heap sort is a build plus n extractions: O(n log n) worst case, in place, not stable.

Pattern: Heap selection / top-k. To keep the k largest items of a stream, hold a min-heap of size k. Its root is the smallest of the current top k, so a new item enters only if it beats the root. That costs O(n log k) time and O(k) space and works on streams too large to store. Alternatives: sorting (O(n log n), simplest), quickselect (O(n) expected but O(n²) worst case, needs all data in memory and reorders it), or bucket counting when keys are small integers (Top K Frequent Elements by frequency buckets is O(n)).

K-way merge. Push the head of each sorted list as (value, list_id, position), then repeatedly pop the minimum and push the next element from the same list. With N items across k lists this is O(N log k). The same frontier idea finds the k smallest pair sums without generating every pair.

Pattern: Two heaps / streaming statistics. For a running median, keep a max-heap for the lower half and a min-heap for the upper half, sizes equal or the lower half one larger. Insert into one side, move its top across if the halves are out of order, then rebalance sizes; the median is the lower top or the mean of both tops. Each insertion is O(log n) and each query O(1). A sliding-window median also needs removals, which library heaps do not support efficiently: record outgoing values as pending deletions, discard them when they surface at a top, and track each heap's effective size.

Library behavior. Python heapq and Java PriorityQueue are min-heaps; C++ std::priority_queue is a max-heap; JavaScript has no built-in heap. For max-heaps over numbers, negate keys or pass a reversed comparator. When payloads are not comparable (list nodes, objects), add a tie-breaking counter so equal priorities never compare payloads. Most library heaps lack decrease-key: push a new entry and skip stale ones when popped. Go's container/heap provides Fix if you track each item's index.

Common misconceptions

• "For the k largest, use a max-heap of everything." That costs O(n) space and O(n + k log n) time; a size-k min-heap uses O(k) space and also works on streams.
• "Building a heap is O(n log n)." Bottom-up heapify is O(n); only n separate insertions cost O(n log n).
• "A heap is a sorted array." Only the root is guaranteed to be the extreme; iterating the underlying array does not give sorted order.
• "Quickselect always beats a heap." Quickselect is O(n) only in expectation, needs all data in memory and mutates it; a heap streams with a guaranteed bound.
• "Changing a priority is cheap." Library heaps cannot find an item quickly; use lazy deletion or an indexed heap that you implement.

How to approach it

When a problem says k largest, k closest, next earliest or median so far, consider a heap and say which kind and why, especially the counterintuitive min-heap for the k largest. State the heap's size bound (k, the number of lists, or n), because it sets the log factor. Interviewers typically ask for an alternative (sorting, quickselect, buckets), the space cost, and how the solution changes for a stream that never ends.