# 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 `k` points in the heap. * For each new point, if the heap has fewer than `k` points → 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. ```python 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. ```python 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. ```python 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+1` slots, try to pick up to `n+1` distinct 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. ```python 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). ```python 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. * `heapify` is 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!