Heap Fundamentals
A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is smaller than its children; in a max-heap, every parent is larger. The minimum (min-heap) or maximum (max-heap) is always at the root — O(1) access. Insert and remove are O(log n). Python provides heapq as a min-heap. To simulate a max-heap, negate values: heappush(heap, -val).
import heapq
# Min-heap
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
smallest = heapq.heappop(min_heap) # 1
# Max-heap (negate values)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
largest = -heapq.heappop(max_heap) # 3
# Heapify in-place: O(n) — more efficient than N pushes
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums) # transforms list into valid min-heap
Pattern 1: Top K Elements
Finding the K largest (or smallest) elements from a stream or large array. Use a min-heap of size K for top-K largest: if a new element is larger than the heap minimum, pop the minimum and push the new element. The heap always contains the K largest seen so far.
# Kth Largest Element in a Stream
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for n in nums:
self.add(n)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # remove smallest
return self.heap[0] # kth largest = heap min
# Top K Frequent Elements
def top_k_frequent(nums, k):
freq = {}
for n in nums:
freq[n] = freq.get(n, 0) + 1
# Min-heap of (frequency, element), size K
heap = []
for num, count in freq.items():
heapq.heappush(heap, (count, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for count, num in heap]
Pattern 2: Merge K Sorted Lists
# Merge K sorted linked lists: O(N log K) where N = total nodes
def merge_k_lists(lists):
heap = [] # (value, list_index, node)
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode()
curr = dummy
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# Same pattern applies to: merge K sorted arrays, K-way external merge sort
Pattern 3: Median of Data Stream
Finding the running median requires efficiently finding the middle element of a dynamically changing dataset. Two-heap approach: a max-heap for the lower half and a min-heap for the upper half. The heaps are balanced (size difference at most 1). The median is the top of the larger heap (odd total) or the average of both tops (even total).
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (lower half) — negate for Python
self.large = [] # min-heap (upper half)
def add_num(self, num):
# Always push to small first
heapq.heappush(self.small, -num)
# Balance: if small max > large min, move to large
if self.small and self.large and (-self.small[0] > self.large[0]):
heapq.heappush(self.large, -heapq.heappop(self.small))
# Rebalance sizes
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
elif len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def find_median(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
Pattern 4: Task Scheduling
# Task Scheduler: given tasks with frequencies and cooldown n,
# find minimum intervals to execute all tasks
def least_interval(tasks, n):
freq = [0] * 26
for t in tasks:
freq[ord(t) - ord("A")] += 1
max_heap = [-f for f in freq if f > 0]
heapq.heapify(max_heap)
time = 0
queue = deque() # (remaining_count, available_at)
while max_heap or queue:
time += 1
if max_heap:
count = 1 + heapq.heappop(max_heap) # decrement (negative)
if count != 0:
queue.append((count, time + n)) # cooldown
if queue and queue[0][1] == time:
heapq.heappush(max_heap, queue.popleft()[0])
return time
# Reorganize String: no two adjacent chars same — greedy with max-heap
def reorganize_string(s):
freq = {}
for c in s:
freq[c] = freq.get(c, 0) + 1
heap = [(-count, char) for char, count in freq.items()]
heapq.heapify(heap)
result = []
while len(heap) >= 2:
c1, ch1 = heapq.heappop(heap)
c2, ch2 = heapq.heappop(heap)
result.extend([ch1, ch2])
if c1 + 1: heapq.heappush(heap, (c1 + 1, ch1))
if c2 + 1: heapq.heappush(heap, (c2 + 1, ch2))
return result[0] if heap and -heap[0][0] == 1 else "" if heap else "".join(result)
Pattern 5: Dijkstra Shortest Path
Dijkstra uses a min-heap to always process the node with the current shortest known distance. This greedy choice works because edge weights are non-negative — the first time a node is popped from the heap, it has its final shortest distance. Each node-distance pair is pushed to the heap when a shorter path is found; stale entries (node popped with a longer distance than currently known) are skipped with a simple check.
def dijkstra(graph, start):
dist = {node: float("inf") for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]: continue # stale entry
for neighbor, weight in graph[node]:
if dist[node] + weight < dist[neighbor]:
dist[neighbor] = dist[node] + weight
heapq.heappush(heap, (dist[neighbor], neighbor))
return dist
Common Heap Interview Problems
- Top K: Kth Largest Element in Array/Stream, Top K Frequent Elements, K Closest Points to Origin
- Merge: Merge K Sorted Lists, Smallest Range Covering Elements from K Lists
- Two-heap: Median of Data Stream, Sliding Window Median
- Scheduling: Task Scheduler, Reorganize String, Meeting Rooms II
- Graph: Dijkstra Shortest Path, Prim Minimum Spanning Tree, Cheapest Flights Within K Stops
Frequently Asked Questions
When should you use a heap (priority queue) in a coding interview?
Use a heap when: (1) You need repeated access to the minimum or maximum of a changing dataset (getting the kth largest element, running median). (2) You need to process items in priority order (task scheduling, Dijkstra shortest path, Prim minimum spanning tree). (3) You need to merge K sorted sequences efficiently (merge K sorted lists, K-way merge). The heap pattern is recognizable by these signals: "find the K largest/smallest," "process in order of some priority," "find the median of a stream," "schedule tasks with cooldown," or any problem that involves a sorted structure that changes over time. The key operations are O(log n) insert and O(log n) extract-min/max, with O(1) peek at the minimum/maximum.
How do you find the Kth largest element efficiently?
Use a min-heap of size K. Initialize with the first K elements. For each subsequent element: if it is larger than the heap minimum, pop the minimum and push the new element. After processing all elements, the heap minimum is the Kth largest. This runs in O(N log K) time — much better than sorting O(N log N) when K is much smaller than N. For finding the Kth largest in an unsorted array in O(N) average time, use QuickSelect: partition around a pivot (like quicksort), but recurse only into the partition containing the Kth element. QuickSelect has O(N) average but O(N^2) worst-case. The heap approach is O(N log K) worst-case and is preferred for streaming data where you cannot see all elements at once.
How does the two-heap pattern work for finding the median of a data stream?
Maintain two heaps: a max-heap for the lower half of the data and a min-heap for the upper half. After each insertion: (1) Push to the max-heap (lower half). (2) If the max-heap top is greater than the min-heap top, move the max-heap top to the min-heap (to maintain the invariant that all lower-half values are smaller than all upper-half values). (3) Balance the heap sizes so they differ by at most 1. The median is: the top of the larger heap if sizes differ (odd total count), or the average of both tops if sizes are equal (even total count). This gives O(log n) insert and O(1) median query. The pattern extends to sliding window median: maintain the two heaps and a "lazy deletion" set for elements that have left the window.
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “When should you use a heap (priority queue) in a coding interview?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Use a heap when: (1) You need repeated access to the minimum or maximum of a changing dataset (getting the kth largest element, running median). (2) You need to process items in priority order (task scheduling, Dijkstra shortest path, Prim minimum spanning tree). (3) You need to merge K sorted sequences efficiently (merge K sorted lists, K-way merge). The heap pattern is recognizable by these signals: “find the K largest/smallest,” “process in order of some priority,” “find the median of a stream,” “schedule tasks with cooldown,” or any problem that involves a sorted structure that changes over time. The key operations are O(log n) insert and O(log n) extract-min/max, with O(1) peek at the minimum/maximum.” } }, { “@type”: “Question”, “name”: “How do you find the Kth largest element efficiently?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Use a min-heap of size K. Initialize with the first K elements. For each subsequent element: if it is larger than the heap minimum, pop the minimum and push the new element. After processing all elements, the heap minimum is the Kth largest. This runs in O(N log K) time — much better than sorting O(N log N) when K is much smaller than N. For finding the Kth largest in an unsorted array in O(N) average time, use QuickSelect: partition around a pivot (like quicksort), but recurse only into the partition containing the Kth element. QuickSelect has O(N) average but O(N^2) worst-case. The heap approach is O(N log K) worst-case and is preferred for streaming data where you cannot see all elements at once.” } }, { “@type”: “Question”, “name”: “How does the two-heap pattern work for finding the median of a data stream?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Maintain two heaps: a max-heap for the lower half of the data and a min-heap for the upper half. After each insertion: (1) Push to the max-heap (lower half). (2) If the max-heap top is greater than the min-heap top, move the max-heap top to the min-heap (to maintain the invariant that all lower-half values are smaller than all upper-half values). (3) Balance the heap sizes so they differ by at most 1. The median is: the top of the larger heap if sizes differ (odd total count), or the average of both tops if sizes are equal (even total count). This gives O(log n) insert and O(1) median query. The pattern extends to sliding window median: maintain the two heaps and a “lazy deletion” set for elements that have left the window.” } } ] }