Heaps (priority queues) are the go-to data structure for problems involving the K-th largest/smallest element, merging sorted sequences, and scheduling by priority. A heap provides O(log N) insert and O(1) peek at the min or max, making it ideal for maintaining a dynamic set of “best” elements. This guide covers the heap patterns most commonly tested in coding interviews.
Pattern 1: Top-K Elements
Find the K largest (or smallest) elements from a collection. Approach: maintain a min-heap of size K. For each element: if the heap has fewer than K elements, push it. If the element is larger than the heap minimum (top), pop the minimum and push the new element. After processing all elements, the heap contains the K largest elements. The root is the K-th largest. Time: O(N log K). Space: O(K). Why min-heap for K largest: the min-heap root is the smallest of the K largest elements. If a new element is larger than this root, it belongs in the top-K (replace the root). If smaller, it does not. This efficiently filters without sorting the entire array. Variations: K-th largest element (return heap root after processing all elements), top K frequent elements (count frequencies with a hash map, then use a min-heap of size K on the frequencies), K closest points to origin (distance as the heap key). QuickSelect alternative: O(N) average for K-th element specifically, but O(N^2) worst case. Heap is O(N log K) guaranteed.
Pattern 2: Merge K Sorted Sequences
Merge K sorted lists (or arrays) into one sorted output. Approach: create a min-heap containing one element from each list (the current head of each list). Repeatedly extract the minimum from the heap, add it to the result, and push the next element from the same list. When a list is exhausted, do not push. Continue until the heap is empty. Time: O(N log K) where N is total elements across all lists and K is the number of lists. Each of the N elements is pushed and popped from a K-sized heap: O(log K) per operation. Space: O(K) for the heap. Why this is efficient: directly merging two lists at a time (like merge sort) takes K-1 merge passes, each O(N). Total: O(N * K). The heap approach is O(N log K) — significantly better when K is large. Applications: merge K sorted linked lists (LeetCode 23), smallest range covering elements from K lists, and external sort (merge sorted chunks from disk). Implementation detail: store (value, list_index, element_index) tuples in the heap so you know which list to advance after extracting the minimum.
Pattern 3: Two Heaps for Median
Find the median from a data stream (elements arrive one at a time). Approach: maintain two heaps: a max-heap for the lower half of elements and a min-heap for the upper half. The max-heap root is the largest element in the lower half. The min-heap root is the smallest in the upper half. Balance: keep the heaps within 1 element in size. Insert: if the new element is less than or equal to the max-heap root, push to the max-heap. Else push to the min-heap. Rebalance: if the max-heap has more than 1 extra element, pop from max-heap and push to min-heap (and vice versa). Median: if heaps are equal size, median = (max_heap_root + min_heap_root) / 2. If one heap is larger, median = its root. Time: O(log N) per insert. O(1) for median. Variations: sliding window median (use two heaps + lazy deletion: mark elements for removal when they leave the window, actually remove when they appear at the heap root), and IPO problem (maximize capital by selecting projects with two heaps: available projects by profit, locked projects by capital).
Pattern 4: Scheduling and Intervals with Heaps
Heaps efficiently manage scheduling problems where you need the “next available” or “earliest ending” resource. Meeting Rooms II: find the minimum number of meeting rooms. Sort meetings by start time. Maintain a min-heap of meeting end times (each entry represents a room in use). For each meeting: if the earliest ending room finishes before this meeting starts (heap root <= meeting start), reuse it (pop and push new end time). Else allocate a new room (push end time). Heap size = rooms needed. Task Scheduler: given tasks with a cooldown, find minimum time. Use a max-heap of task frequencies. Each cycle: pop up to N+1 tasks from the heap (execute the most frequent tasks), decrement their counts, push non-zero counts back after the cooldown. Reorganize String: rearrange so no two adjacent characters are same. Max-heap of character frequencies. Each step: pop the most frequent, append to result, push back with decremented count. Keep the previously popped character aside for one step (to prevent adjacency). These problems share the pattern: use a heap to select the optimal next action (earliest ending, highest frequency, best fit).
Heap Implementation Tips for Interviews
Language-specific: Python heapq is a min-heap. For max-heap: negate values (push -value, pop gives -max which you negate back). Java PriorityQueue is a min-heap by default. For max-heap: pass Collections.reverseOrder() or a custom comparator. Go container/heap requires implementing the Heap interface. Custom comparators: for complex objects (merge K lists: compare by value, track list index), use tuples in Python: heapq.heappush(heap, (value, list_idx, elem_idx)). Python compares tuples element by element, so value is the primary sort key. Common mistakes: (1) Forgetting that Python heapq is min-heap (using it as max-heap without negation). (2) Not handling the K=0 edge case for top-K problems. (3) For merge K sorted: not checking if a list is exhausted before pushing the next element. (4) For two-heap median: not rebalancing after every insert. When to use heap vs sorting: heap is better when elements arrive dynamically (streaming) or when you only need the top-K (not the full sorted order). Sorting is better when you need the complete sorted output and all elements are available upfront.