Heap Patterns — Priority Queue Guide

A heap is a specialized tree-based data structure that gives you O(log n) insertions and O(log n) deletions of the minimum (or maximum) element, plus O(1) access to that extreme value. The core use case is repeated extraction of the minimum or maximum from a dynamically changing collection. When the problem requires you to do this many times — not just once — a heap almost always outperforms sorting the entire array each time.

The clearest signal that a heap is the right tool is when the problem involves the word "kth" or "top k." Problems like "find the kth largest element," "return the k closest points to the origin," or "find the k most frequent elements" all fit the heap template exactly. A second strong signal is streaming or online data: when elements arrive one at a time and you must maintain a running answer (like a running median), a heap gives you the efficient incremental update you need.

Scheduling problems are a third signal — when tasks have priorities and you always want to process the highest-priority task next, a max-heap implements a priority queue directly. Any time you find yourself reaching for sorted order but only actually using the top of the sorted list repeatedly, replace the sort with a heap.

A min-heap keeps the smallest element at the top. Every parent node is smaller than or equal to its children, so a pop() always removes and returns the current minimum. A max-heap keeps the largest element at the top — every parent is greater than or equal to its children, so a pop() removes the current maximum. Both operations run in O(log n) time because they restore the heap property by bubbling up or sinking down through at most the tree's height.

The counterintuitive insight that trips up many candidates: to find the k largest elements in an array, you use a min-heap — not a max-heap. You maintain a min-heap of size k. As you iterate through the array, you push each element. If the heap grows beyond k, you pop the minimum. After processing all elements, the heap contains exactly the k largest values, and the heap top is the kth largest. The min-heap evicts the smallest elements, leaving the largest survivors.

Python's heapq module only provides a min-heap. To simulate a max-heap, negate your values on push and negate again on pop. Java's PriorityQueue defaults to min order; pass Comparator.reverseOrder() to the constructor for a max-heap. Both languages give you O(log n) push and pop and O(1) peek at the top element.

The top-k pattern is the most common heap pattern in LeetCode problems. The algorithm is: maintain a min-heap of size at most k. For each element, push it onto the heap. If the heap size exceeds k, pop the minimum. After processing all n elements, the heap contains exactly the k largest elements in O(n log k) time and O(k) space. This beats sorting the entire array in O(n log n) time whenever k is much smaller than n.

The pattern applies directly to "kth largest element" (the heap top after processing is the answer), "k closest points to origin" (push (distance, point) tuples; heap of size k retains closest k), and "top k frequent elements" (first count frequencies with a hash map, then apply the top-k heap to (frequency, element) pairs). All three problems reduce to the same four-line heap loop.

A common variant asks for the kth smallest instead. Use a max-heap of size k: push each element; if size exceeds k, pop the maximum. The max-heap evicts large elements, keeping the k smallest. In Python, negate values to convert heapq into a max-heap. In Java, use PriorityQueue with Comparator.reverseOrder().

The k-way merge pattern solves problems that require merging k sorted sequences into one globally sorted result. The algorithm uses a min-heap initialized with the first element from each of the k lists (along with a pointer tracking which list it came from). Each iteration: pop the globally smallest element from the heap, add it to the result, then push the next element from that same list. Repeat until the heap is empty. Total time is O(n log k) where n is the total number of elements across all lists.

This pattern appears directly in "merge k sorted lists" (LeetCode 23), where each list is a linked list and the heap stores (node.val, list_index, node) tuples. It also appears in "find the smallest range covering elements from k lists" (LeetCode 632), where you maintain a sliding window using a heap to track the current minimum and a variable to track the current maximum across all k lists simultaneously.

The k-way merge is also the right approach for problems involving multiple sorted arrays, sorted files, or any scenario where you have k sorted streams and need to process elements in global sorted order without loading everything into memory at once. The heap acts as a priority router between streams.

The two-heap pattern for maintaining a running median uses two heaps that together represent the sorted order of all elements seen so far. A max-heap (lower half) stores the smaller half of the elements; a min-heap (upper half) stores the larger half. The invariant is that lower_max <= upper_min at all times, and the two heaps differ in size by at most one element. The median is either the top of the larger heap (odd total count) or the average of both tops (even total count).

On each insert, decide which heap receives the new element: if the value is less than or equal to the max-heap top, push to the max-heap; otherwise push to the min-heap. Then rebalance: if either heap is more than one element larger than the other, pop from the larger heap and push to the smaller. Each insert is O(log n) and each median query is O(1). This is optimal — any data structure supporting both operations must spend at least O(log n) per insert.

This pattern solves "find median from data stream" (LeetCode 295) directly. The "sliding window median" (LeetCode 480) is a harder variant that requires both inserting new elements and removing outgoing elements from the window. Standard heaps do not support efficient arbitrary removal, so the solution uses lazy deletion: mark removed elements as invalid and skip them when they reach the top of a heap.

Python's heapq module operates on a plain list and treats it as a min-heap. The key functions are heapq.heappush(heap, item) to add an element, heapq.heappop(heap) to remove and return the minimum, and heap[0] to peek at the minimum without removing it. To build a heap from an existing list in O(n) time, use heapq.heapify(list). For tuples, Python compares element by element, so (priority, value) tuples work naturally for priority queues. Negate the value for a max-heap: push -x and pop then negate the result.

Java's PriorityQueue<T> class is a min-heap by default using the natural ordering of T. Add elements with offer(x) or add(x); remove and return the minimum with poll(); peek at the minimum with peek(). For a max-heap, pass a comparator: new PriorityQueue<>(Comparator.reverseOrder()). For custom objects, implement Comparable<T> or pass a lambda comparator such as (a, b) -> a.dist - b.dist. Java's PriorityQueue does not support indexed access — you cannot read element at position i without polling.

Both implementations offer O(log n) push and pop and O(n) heapify. Neither supports O(log n) decrease-key (updating an element's priority in place). This matters most for Dijkstra's algorithm, where the textbook version uses decrease-key. The interview workaround is to push duplicate (new_distance, node) entries and skip stale ones when you pop: if the popped distance is greater than the known shortest distance, discard it and continue.

The recommended heap study path starts with pure top-k problems where the heap template applies almost verbatim, then moves to k-way merge problems that require managing multiple pointers, and finishes with the two-heap median pattern and scheduling problems that combine heaps with greedy reasoning. Working through problems in this order lets you build the heap intuition incrementally before tackling problems that combine heap mechanics with additional algorithmic ideas.

For easy warm-up problems, start with "kth largest element in a stream" (LeetCode 703) — it is literally the top-k pattern with a streaming wrapper. For medium problems, "top k frequent elements" (LeetCode 347), "k closest points to origin" (LeetCode 973), "merge k sorted lists" (LeetCode 23), and "task scheduler" (LeetCode 621) each exercise a distinct heap pattern. For hard problems, "find median from data stream" (LeetCode 295), "sliding window median" (LeetCode 480), and "the skyline problem" (LeetCode 218) all require the two-heap or multi-heap approach.

For interview preparation, being fluent with the top-k pattern and k-way merge covers the vast majority of heap questions in FAANG-style interviews. The two-heap median and Dijkstra-with-heap patterns are the stretch goals for senior-level rounds. Practice implementing a clean min-heap loop in both Python (heapq) and Java (PriorityQueue) until the four-line top-k template is automatic.