Mastering Heaps & Priority Queues
Welcome back to our algorithm deep‑dive. By now you’ve probably noticed that certain problems keep appearing in coding interviews – and many of them have a secret weapon: heaps (also known as priority queues). In this hour, we’ll break down heaps from the ground up, tackle classic LeetCode challenges, and show you how to recognise when a heap is the right tool for the job.
We’ll cover:
Min‑heap vs Max‑heap and why the difference matters.
The magic of
heapify– building a heap in O(n).Real‑world problems: K Closest Points to Origin, Top K Frequent Elements, Median Finder, Task Scheduler, and Reorganize String.
Let’s jump in.
Min‑Heap vs Max‑Heap – A Tale of Two Priorities
A heap is a binary tree that satisfies the heap property:
Min‑heap – the smallest element is always at the root. Every parent is ≤ its children.
Max‑heap – the largest element is at the root. Every parent is ≥ its children.
| Min‑heap | Max‑heap |
|---|---|
| Root = global minimum | Root = global maximum |
| Efficient for “get smallest” | Efficient for “get largest” |
| Used in Dijkstra, Prim, scheduling | Used in sorting (heapsort), task prioritisation |
Most languages provide a priority queue (e.g., heapq in Python, PriorityQueue in Java). By default they are min‑heaps – but you can simulate a max‑heap by storing negative values.
Heapify – Why O(n) Matters
If you insert n elements one by one into an empty heap, you spend O(n log n) time. But there’s a faster way: heapify.
heapify turns any array into a heap in O(n) time, not O(n log n).
How? It works from the last non‑leaf node upwards, “bubbling down” each element. The math behind it is beautiful – most nodes are near the leaves, so they only sink a few levels. The total number of swaps is linear in n.
Why should you care?
Because when you need to build a heap from an existing list (e.g., the K Closest Points problem), heapify saves you a full log factor. In practice, it’s the difference between a solution that passes and one that times out on large inputs.
1. K Closest Points to Origin (LeetCode 973)
Problem: Given an array of (x, y) points and an integer k, return the k closest points to the origin (0,0).
Heap insight: We only care about the distance² (to avoid floating point). A max‑heap of size k works perfectly:
Keep at most
kpoints in the heap.For each new point, if the heap has fewer than
kpoints → push it.Else, if its distance is smaller than the largest distance in the heap → pop the largest and push the new one.
At the end, the heap contains exactly the k closest points.
Why a max‑heap? Because we want to quickly remove the farthest point among the current candidates.
import heapq
def kClosest(points, k):
# max-heap via negative distance
heap = []
for x, y in points:
dist = -(x*x + y*y) # negative for max-heap
if len(heap) < k:
heapq.heappush(heap, (dist, x, y))
else:
if dist > heap[0][0]: # is current point closer?
heapq.heapreplace(heap, (dist, x, y))
return [(x, y) for (_, x, y) in heap]
Time complexity: O(n log k) – excellent when k is small.
2. Top K Frequent Elements (LeetCode 347)
Problem: Given an integer array, return the k most frequent elements.
Heap insight: First build a frequency map (O(n)). Then we need the k elements with the highest frequencies. A min‑heap of size k is ideal:
Push pairs
(frequency, element)into the heap.If heap size > k, pop the smallest frequency (the least frequent among the candidates).
Why a min‑heap? Because we want to evict the element with the lowest frequency as we go. After processing all frequencies, the heap holds the k largest ones.
def topKFrequent(nums, k):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
heap = []
for num, f in freq.items():
heapq.heappush(heap, (f, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for (f, num) in heap]
Time complexity: O(n log k) – fast and memory efficient.
3. Median Finder (Two Heaps) – LeetCode 295
Problem: Design a data structure that supports adding a number and finding the median of all added numbers.
Heap insight: This is the classic two‑heap pattern:
A max‑heap for the lower half (all elements ≤ median).
A min‑heap for the upper half (all elements ≥ median).
We maintain the invariant that the lower half is either equal in size or one element larger than the upper half. Then the median is:
If sizes differ → root of max‑heap.
If equal → (root of max‑heap + root of min‑heap) / 2.
class MedianFinder:
def __init__(self):
self.lower = [] # max-heap (store negatives)
self.upper = [] # min-heap
def addNum(self, num):
# Push to lower first (as negative for max-heap)
heapq.heappush(self.lower, -num)
# Balance: move largest of lower to upper
heapq.heappush(self.upper, -heapq.heappop(self.lower))
# Ensure lower size >= upper size
if len(self.lower) < len(self.upper):
heapq.heappush(self.lower, -heapq.heappop(self.upper))
def findMedian(self):
if len(self.lower) > len(self.upper):
return -self.lower[0]
return (-self.lower[0] + self.upper[0]) / 2.0
Every addition is O(log n). This is the gold standard for dynamic median problems.
4. Task Scheduler (LeetCode 621)
Problem: Given a list of tasks (each represented by a letter) and a cooldown n, you must schedule tasks so that the same task has at least n idle slots between executions. Find the minimum number of CPU cycles needed.
Heap insight: Greedy + max‑heap. Always schedule the most frequent available task first.
Count frequencies, push them into a max‑heap.
In each cycle of
n+1slots, try to pick up ton+1distinct tasks (the ones with highest remaining counts).Decrease counts and push back if still positive.
Why a max‑heap? Because at every decision point, we want the task with the highest remaining frequency – that minimises future idle time.
def leastInterval(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)
cycles = 0
while max_heap:
temp = []
for _ in range(n+1):
if max_heap:
cnt = -heapq.heappop(max_heap)
if cnt > 1:
temp.append(cnt-1)
cycles += 1
if not max_heap and not temp:
break
for item in temp:
heapq.heappush(max_heap, -item)
return cycles
This runs in O(total tasks) with heap operations O(log 26) – practically constant.
5. Reorganize String (LeetCode 767)
Problem: Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any possible rearrangement, or "" if impossible.
Heap insight: Almost identical to Task Scheduler (with n = 1). Use a max‑heap based on character frequency. Always pick the most frequent character that is not the same as the previously placed one.
If at some point the heap is empty but characters remain → impossible (the maximum frequency is more than half+1).
def reorganizeString(s):
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
max_heap = [(-cnt, ch) for ch, cnt in freq.items()]
heapq.heapify(max_heap)
res = []
prev_cnt, prev_ch = 0, ''
while max_heap:
cnt, ch = heapq.heappop(max_heap)
res.append(ch)
if prev_cnt < 0:
heapq.heappush(max_heap, (prev_cnt, prev_ch))
prev_cnt, prev_ch = cnt+1, ch # cnt+1 because cnt is negative
return ''.join(res) if len(res) == len(s) else ""
The check at the end ensures feasibility: if the most frequent character appears more than (len(s)+1)//2 times, it’s impossible.
Key Takeaways
Min‑heap → quick access to smallest; Max‑heap → quick access to largest.
heapifyis O(n) – use it when you already have all elements.Two‑heap pattern (lower max + upper min) is perfect for running medians.
Top‑k problems often use a heap of size k – either min or max depending on whether you want the largest or smallest elements.
Scheduling problems (Task Scheduler, Reorganize String) are beautifully solved by greedily picking the most frequent available task.
Heaps won’t solve every problem, but once you recognise a scenario that demands “the smallest/largest among the most recent k” or “maintain a running median”, you’ll reach for a priority queue without thinking twice.
Now go practice these five LeetCode problems.
Happy coding!
