Chapter 6 · Intermediate · Prereq: Chapter 5

Heaps & Priority Queues

Master the data structure powered by complete binary trees. Learn to pinpoint Top-K problems, merge K sorted lists, and track rolling medians efficiently.

11 Sections 8 Practice Problems Intermediate ← Back to Roadmap

Section 1 — What Is a Heap?

A heap is a complete binary tree stored as a flat array satisfying the heap property: every parent is >= its children (max-heap) or <= its children (min-heap). This guarantees O(1) access to the extreme element and O(log n) insert / delete.

Real-World Analogy: Hospital ER

Patients arrive with different severity levels — the most critical patient is always treated next (root node).
A new critical patient jumps ahead of less-critical ones already waiting.
Each arrival (push) and each treatment (pop) costs O(log n) to maintain order.

1.1 — Tree-to-Array Mapping

Because it's a complete binary tree (nodes filled left-to-right), there are zero wasted slots. No pointers needed.

Tree vs Array Representation

Max-Heap tree:           Stored as array (0-indexed):

       10                Index: [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6]
      /  \               Value: [10] [ 9] [ 8] [ 7] [ 6] [ 5] [ 4]
     9    8
    / \  / \
   7   6 5   4

Arithmetic for finding relatives of node `i`:
- Parent:      (i - 1) / 2
- Left child:  2*i + 1
- Right child: 2*i + 2

1.2 — Min-Heap vs Max-Heap

Property	Min-Heap	Max-Heap
Root	Minimum value	Maximum value
Parent Rule	Parent `<=` Children	Parent `>=` Children
`peek()`	Returns minimum `O(1)`	Returns maximum `O(1)`
C++ STL	`priority_queue<int, vector<int>, greater<int>>`	`priority_queue<int>` (default)
Use cases	Top-K smallest, Dijkstra, K-way merge	Top-K largest, CPU scheduling

Section 2 — Core Operations

2.1 — Insert (Sift Up) — `O(log n)`

To insert, append the new element to the end of the array (bottom of the tree). Then, continuously swap it with its parent if it violates the heap property (sifting it "up").

2.2 — Extract Max/Min (Sift Down) — `O(log n)`

To extract the root, swap it with the very last element in the array. Remove the last element (the answer). Now the root is wrong. Swap the new root with its largest (or smallest) child until the heap property is restored (sifting it "down").

The Top-K Paradox

To find the top-K LARGEST elements, use a MIN-heap of size K.

The heap strictly holds the "K largest seen so far".
The root is the smallest of that elite group (the "weakest link").
When a new element arrives, if it's strictly greater than the root, it beats the weakest link. Pop the root and push the new element.

Section 3 — C++ Implementation Guide

3.1 — Priority Queue API

C++ priority_queue

#include <queue>

// MAX-HEAP (Default)
priority_queue<int> maxH;       
maxH.push(5);    // O(log n)
maxH.top();      // O(1) - Returns 5
maxH.pop();      // O(log n) - Removes 5. Returns void!

// MIN-HEAP
priority_queue<int, vector<int>, greater<int>> minH;

// PAIR HEAP (e.g. Dijkstra)
// Ordered by first element ascending
using P = pair<int, int>;
priority_queue<P, vector<P>, greater<P>> pq_pairs;

// O(n) HEAPIFY FROM VECTOR
vector<int> v = {3, 1, 4, 1, 5};
priority_queue<int> h(v.begin(), v.end()); // Better than pushing n times!

3.2 — Custom Comparators

When you need to order objects dynamically (e.g., frequencies), use a lambda comparator.

Custom Min-Heap

auto cmp = [](pair<int,string> a, pair<int,string> b){
    return a.first > b.first; // Note standard reverse operator orientation! MIN-heap on frequency
};
// Use decltype for lambdas
priority_queue<pair<int,string>, vector<pair<int,string>>, decltype(cmp)> customH(cmp);

Section 4 — Two-Heap Pattern (Median of Stream)

A classic architecture pattern is tracking a moving median using two balanced heaps. This guarantees O(log n) inserts and O(1) reads.

Lower Half

Max-Heap: Stores the smaller half of numbers. Root = largest of the smalls.

Upper Half

Min-Heap: Stores the larger half of numbers. Root = smallest of the bigs.

Two Invariants

Every element in lower half <= every element in upper half (lo.top() <= hi.top()).
Sizes differ by at most 1. Generally, if odd elements, the extra lives in lo.

LeetCode 295: Find Median from Data Stream

class MedianFinder {
    priority_queue<int> lo;                               // max-heap
    priority_queue<int, vector<int>, greater<int>> hi;    // min-heap
public:
    void addNum(int num) {
        lo.push(num); // 1. Always push lower first
        
        // 2. Fix ordering violation (Invariant 1)
        if (!hi.empty() && lo.top() > hi.top()) {
            hi.push(lo.top()); lo.pop();
        }
        
        // 3. Rebalance (Invariant 2)
        if (lo.size() > hi.size() + 1) {
            hi.push(lo.top()); lo.pop();
        } else if (hi.size() > lo.size()) {
            lo.push(hi.top()); hi.pop();
        }
    }
    
    double findMedian() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

Section 5 — Practice Problems & Patterns

Pattern Trigger	Action
"Kth Largest Element"	Min-Heap of size K
"Kth Smallest Element"	Max-Heap of size K
"Top K Frequent"	Build HashMap counts → Min-Heap of size K
"Merge K Sorted Lists/Arrays"	Min-Heap storing heads `(value, list_idx)`
"Shortest Path in Weighted Graph"	Dijkstra (Min-Heap of `(distance, node_id)`)
"Data Stream Median"	Two-Heap (Max lower, Min upper)

Practice Checklist

#	Problem	Difficulty	Pattern
1	1962. Remove Stones	Medium	Max-Heap
2	1167. Connect Sticks	Medium	Min-Heap
3	215. Kth Largest	Medium	Top K
4	973. K Closest Points	Medium	Top K
5	703. Kth Largest Stream	Easy	Top K
6	295. Find Median	Hard	Two Heaps
7	621. Task Scheduler	Medium	Max-Heap + Queue
8	23. Merge K Lists	Hard	Min-Heap (K-way)