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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you find the K-th largest element using a heap?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain a min-heap of size K. Process each element: if heap has fewer than K elements, push it. If the element is larger than the heap root (minimum of the K largest so far), pop the root and push the new element. After processing all N elements, the heap root is the K-th largest. Time: O(N log K). Space: O(K). Why min-heap for K largest: the root is the smallest among the K largest elements. Any element smaller than this root is not in the top-K. Any element larger replaces the root. This efficiently filters without sorting. Variations: top K frequent elements (hash map for frequencies, then min-heap of size K on frequencies), K closest points (distance as heap key), K-th smallest (use a max-heap of size K instead). QuickSelect is O(N) average for K-th element but O(N^2) worst case. Heap guarantees O(N log K).”}},{“@type”:”Question”,”name”:”How does the two-heap technique find the median from a data stream?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain two heaps: a max-heap for the lower half 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. Insert: if new element <= max-heap root, push to max-heap. Else push to min-heap. Rebalance: keep heaps within 1 element in size. If one grows too large, pop its root and push to the other. Median: if equal size, average both roots. If one is larger, its root is the median. Time: O(log N) per insert, O(1) for median. The key insight: the two heaps maintain a sorted partition of all elements. The max-heap root and min-heap root are always the two middle elements, giving instant median access. Extension: sliding window median adds lazy deletion — mark elements for removal, actually delete when they appear at the heap root."}},{"@type":"Question","name":"How do you merge K sorted lists efficiently with a heap?","acceptedAnswer":{"@type":"Answer","text":"Create a min-heap containing one element from each of the K lists (each list current head). Repeatedly: extract the minimum from the heap (this is the next element in the merged output), push the next element from the same list into the heap. When a list is exhausted, do not push. Continue until the heap is empty. Time: O(N log K) where N is total elements. Each of N elements is pushed/popped from a K-sized heap: O(log K) per operation. Without a heap: merging two lists at a time requires K-1 passes of O(N) each = O(NK). The heap approach is significantly better for large K. Store (value, list_index, element_index) tuples so you know which list to advance. Python: heapq handles tuple comparison automatically (compares first element, then second for ties)."}},{"@type":"Question","name":"What scheduling problems are solved with heaps?","acceptedAnswer":{"@type":"Answer","text":"Heaps select the optimal next action by priority. Meeting Rooms II: min-heap of end times. For each meeting (sorted by start): if earliest-ending room finishes before this meeting starts, reuse it (pop, push new end). Else allocate new room (push). Heap size = rooms needed. Task Scheduler with cooldown: max-heap of task frequencies. Each cycle: pop up to N+1 most frequent tasks, execute them, push back with decremented counts. Idle slots fill gaps. Reorganize String: max-heap of character frequencies. Pop most frequent, append to result, hold it aside for one step (prevent adjacency), push back next iteration. IPO / Capital Allocation: two heaps — max-heap of profits for available projects, min-heap of capitals for locked projects. Each round: unlock projects whose capital requirement is met, select the most profitable available project. Pattern: use a heap whenever you need to repeatedly select the best/worst/earliest element from a dynamic collection."}}]}