Heap Structure & Properties
100 ← Max-Heap: parent ≥ children
/ \
19 36 ← Stored as array: [100,19,36,17,3,25,1]
/ \ / \
17 3 25 1
Array index: parent(i) = (i-1)/2, left = 2i+1, right = 2i+2
Max-Heap: Root is always the maximum. Push/pop = O(log n).
Min-Heap: Root is always minimum. Default in many languages.
C++ priority_queue API
C++
#include <queue>
// MAX-HEAP (default in C++) — largest element on top
priority_queue<int> maxH;
maxH.push(5);
maxH.push(1);
maxH.push(9);
maxH.top(); // → 9 (max element) O(1)
maxH.pop(); // removes 9 O(log n)
maxH.size(); // → 2
maxH.empty(); // → false
// MIN-HEAP — smallest element on top
priority_queue<int, vector<int>, greater<int>> minH;
minH.push(5); minH.push(1); minH.push(9);
minH.top(); // → 1 (min element)
// HEAP of pairs — by default sorts by first element descending
priority_queue<pair<int,int>> pairH;
pairH.push({3, 100}); // {frequency, value}
pairH.push({5, 200});
pairH.top(); // → {5, 200}
// Build heap from existing array — O(n)
vector<int> v = {3,1,4,1,5};
priority_queue<int> h(v.begin(), v.end()); // O(n) heapify
Core Heap Patterns
Pattern 1: Top K Elements
Keep a min-heap of size K. For each new element, if it's larger than heap top, pop and push. After all elements, heap contains top K largest.
Pattern 2: K-way Merge
Push first element of each sorted list into min-heap with list index. Pop minimum, push next from same list. Merges K sorted lists in O(n log K).
Pattern 3: Running Median
Two heaps: max-heap for lower half, min-heap for upper half. Balance sizes to differ by at most 1. Median = top of larger heap (or average of both tops).
Pattern 4: Dijkstra / Greedy
Min-heap drives greedy selection: always process the cheapest/closest element next. O((V+E) log V) for shortest paths.
Interactive: Min-Heap Push & Pop with Sift
Start with min-heap [1,4,7,9,5]. First: push 3 (appears at bottom, sifts up past 7 and 4 until heap property holds). Then: pop-min (root 1 → last element placed at root, sifts down). Watch the array form in each caption — it reinforces heap-as-array indexing.
Deeper Understanding
🧠 Under the Hood
A heap is stored as a contiguous array — no pointers needed. The parent-child relationship is purely arithmetic. This gives excellent cache performance: sift-up/sift-down access memory in a predictable order. std::priority_queue wraps a std::vector using exactly this layout.
⚖️ When to Use / When NOT to Use
✅ Use heap for "top K" elements from a large or streaming dataset
A min-heap of size K tracks the K largest elements seen so far. Each new element: O(log K) push; if heap exceeds K, O(log K) pop. Total: O(n log K) — beats sorting O(n log n) when K ≪ n.
✅ Use heap for streaming median (two-heap technique)
One max-heap (lower half) + one min-heap (upper half). Maintain sizes within 1 of each other. Median = top of larger heap or average of both tops. All ops O(log n).
✅ Use heap for Dijkstra's shortest path (non-negative weights)
Min-heap drives greedy: always process the closest unvisited node next. O((V+E) log V) total — faster than Bellman-Ford's O(VE) for dense graphs.
❌ Avoid heap when you need arbitrary deletion or search by value
Instead: Use
std::set (RB-tree) — O(log n) for insert, delete-by-value, and ordered iteration. Heap only supports O(1) peek-min and O(log n) pop-min.❌ Avoid heap if you just want the single maximum/minimum
Instead: Use
std::max_element / std::min_element — a single O(n) scan. Building a heap is also O(n) but adds code complexity.🚫 Common Misconceptions
❌ "A heap is fully sorted"
Only the root is guaranteed to be min/max. Siblings at the same level can be in any relative order. Heap sort produces a fully sorted array, but the heap structure itself is only partially ordered.
❌ "std::priority_queue is a min-heap by default"
C++'s
priority_queue is a max-heap by default (largest on top). For a min-heap, use priority_queue<int, vector<int>, greater<int>>. This trips up candidates expecting Python's heapq behavior.❌ "Building a heap is O(n log n)"
Building a heap from an existing array is O(n) using the sift-down approach (start from last non-leaf and sift down). Only repeated insertion (n × O(log n)) is O(n log n). C++ range constructor uses the O(n) build.
🎤 Interview Follow-ups
Why is build-heap O(n) not O(n log n)?
Most nodes are near the leaves and sift very little. The total work sums to O(n) (geometric series argument). Only the root may sift O(log n) levels — and there's only one root.
How does the two-heap median pattern work?
Always push to max-heap (lo), then move max-of-lo to min-heap (hi) to balance. If hi is larger, move its min back to lo. This keeps sizes within 1 of each other. Median is always the top of the larger heap.
When would you use a d-ary heap instead of binary?
A d-ary heap (branching factor d) reduces height to log_d(n) — fewer comparisons during extract-min, but more comparisons per sift-down step. Optimal for Dijkstra on dense graphs: d ≈ E/V reduces total work.
Practice Problems
#703Kth Largest Element in a StreamEasy
Design a class that maintains the kth largest element as new numbers are added to a stream.
Pattern: Min-heap of size k. Kth largest = heap top. If new element > top or heap size < k, add it and trim to k.
C++
class KthLargest {
priority_queue<int, vector<int>, greater<int>> minH;
int k;
public:
KthLargest(int k, vector<int>& nums) : k(k) {
for (int n : nums) add(n);
}
int add(int val) {
minH.push(val);
if (minH.size() > k) minH.pop(); // remove smallest
return minH.top(); // kth largest = min of top-k set
}
};
#215Kth Largest Element in an ArrayMedium
Find the kth largest element in an unsorted array. Not kth distinct.
Pattern 1: Min-heap size k. Pattern 2 (optimal): Quickselect — partition around pivot, recurse only on relevant side. Average O(n).
C++
// Min-heap approach — O(n log k)
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minH;
for (int n : nums) {
minH.push(n);
if (minH.size() > k) minH.pop();
}
return minH.top();
}
// Quickselect — O(n) average, O(n²) worst
int quickselect(vector<int>& A, int l, int r, int k) {
int pivot = A[r], p = l;
for (int i=l; i<r; i++) if(A[i]>=pivot) swap(A[i], A[p++]);
swap(A[p], A[r]);
if (p==k) return A[p];
return p<k ? quickselect(A,p+1,r,k) : quickselect(A,l,p-1,k);
}
int findKthLargest2(vector<int>& nums, int k) {
return quickselect(nums, 0, nums.size()-1, k-1);
}
#347Top K Frequent ElementsMedium
Return k most frequent elements. Order doesn't matter.
Pattern: Frequency map + min-heap of size k (keyed by frequency). Or bucket sort O(n).
C++
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> freq;
for (int n : nums) freq[n]++;
// min-heap of (frequency, value), size k
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> minH;
for (auto& [v,f] : freq) {
minH.push({f, v});
if (minH.size() > k) minH.pop();
}
vector<int> res;
while (!minH.empty()) { res.push_back(minH.top().second); minH.pop(); }
return res;
}
// Time: O(n log k) Space: O(n)
#973K Closest Points to OriginMedium
Return k closest points to origin (0,0). Distance = sqrt(x²+y²) but we can compare x²+y² directly.
Pattern: Max-heap of size k by distance. When heap exceeds k, pop the farthest. Remaining k are closest.
C++
vector<vector<int>> kClosest(vector<vector<int>>& pts, int k) {
// max-heap: (dist², index), keeps closest k by evicting largest
priority_queue<pair<int,int>> maxH;
for (int i=0; i<pts.size(); i++) {
int d = pts[i][0]*pts[i][0] + pts[i][1]*pts[i][1];
maxH.push({d, i});
if (maxH.size() > k) maxH.pop();
}
vector<vector<int>> res;
while (!maxH.empty()) { res.push_back(pts[maxH.top().second]); maxH.pop(); }
return res;
}
// Time: O(n log k) Space: O(k)
#23Merge K Sorted ListsHard
Merge k sorted linked lists and return one sorted list.
Pattern: Min-heap of (node value, node pointer). Push first node of each list. Pop min, push its next. Runs in O(n log k) where n = total nodes.
C++
struct ListNode { int val; ListNode* next; };
ListNode* mergeKLists(vector<ListNode*>& lists) {
// min-heap: (value, node*) — compare by value
auto cmp = [](auto a, auto b){ return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minH(cmp);
for (auto l : lists) if (l) minH.push(l);
ListNode dummy(0); ListNode* cur = &dummy;
while (!minH.empty()) {
ListNode* node = minH.top(); minH.pop();
cur->next = node; cur = cur->next;
if (node->next) minH.push(node->next);
}
return dummy.next;
}
// Time: O(n log k) Space: O(k)
#295Find Median from Data StreamHard
Design a class that supports addNum and findMedian operations on a stream of integers.
Pattern: Two heaps. Max-heap for left half, min-heap for right half. Balance sizes. Median = top of larger heap or average of both tops.
C++
class MedianFinder {
priority_queue<int> lo; // max-heap (left half)
priority_queue<int, vector<int>, greater<int>> hi; // min-heap (right half)
public:
void addNum(int n) {
lo.push(n);
hi.push(lo.top()); lo.pop(); // always push to hi via lo
if (lo.size() < hi.size()) { lo.push(hi.top()); hi.pop(); }
}
double findMedian() {
return lo.size() > hi.size()
? lo.top()
: (lo.top() + hi.top()) / 2.0;
}
};
// addNum: O(log n) findMedian: O(1)
#621Task SchedulerMedium
Given CPU tasks with cooldown n between same tasks. Return minimum intervals to finish all tasks.
Pattern: Max-heap (frequencies) + cooldown queue. Each round: pop most frequent task, execute it, put in cooldown queue with (freq-1, ready_time). Push back when ready.
C++
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char,int> freq;
for (char t : tasks) freq[t]++;
priority_queue<int> maxH;
for (auto& [c,f] : freq) maxH.push(f);
queue<pair<int,int>> cooldown; // (remaining_freq, ready_time)
int time = 0;
while (!maxH.empty() || !cooldown.empty()) {
time++;
if (!maxH.empty()) {
int f = maxH.top()-1; maxH.pop();
if (f > 0) cooldown.push({f, time+n});
}
if (!cooldown.empty() && cooldown.front().second == time)
{ maxH.push(cooldown.front().first); cooldown.pop(); }
}
return time;
}
// Time: O(n log n) Space: O(1) since at most 26 task types
Heap complexity cheat sheet: Push/Pop = O(log n). Peek top = O(1). Build from array = O(n). Use min-heap for "find k largest" (evict smallest). Use max-heap for "find k smallest" (evict largest).
Phase 2 complete! You now know all 7 core data structures in C++. Move to Phase 3: Algorithms to learn Sorting, Searching, DP, Greedy, Backtracking, and more.