stl · advanced

STL: priority_queue — Binary Heap Internals, O(n) Build, Top-K Patterns

std::priority_queue is a binary max-heap backed by a contiguous vector (or deque). Heap property: parent >= both children; max element always at index 0 (root). Array layout: parent(i) = (i-1)/2; left = 2i+1; right = 2i+2 — no pointers, cache-friendly. push: append at end, sift up (swap with parent while larger) — O(log n). pop: swap root with last, remove last, sift down (swap with larger child while smaller) — O(log n). top: return index 0 — O(1). Build from array: Floyd O(n) — sift-down from n/2-1 to 0; sum of heights = O(n). Min-heap: use greater<T> as comparator. Custom comparator: cmp(a,b)=true means a has lower priority (b comes first) — inverted from sort. Interview patterns: top-K (min-heap size k), Dijkstra (min-heap on dist), k-way merge (min-heap of list heads), median streaming (two heaps).

The code

// std::priority_queue — binary max-heap over a contiguous array
// Heap property: parent >= both children (max-heap)
// NOT sorted! — only parent ≥ children guaranteed

// Default: max-heap (largest on top)
priority_queue<int> pq;
pq.push(10); // O(log n) — insert at end, sift up
pq.push(5);
pq.push(20); // 20 sifts to root (violates heap → swap up)
pq.push(3);
pq.top(); // O(1) — root = max element
pq.pop(); // O(log n) — remove root, sift last element down

// Min-heap: reverse comparator
priority_queue<int, vector<int>, greater<int>> minpq;

// Custom comparator for struct:
struct Task {
    int priority;
    string name;
};
auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority; // max-heap on priority
};
priority_queue<Task, vector<Task>, decltype(cmp)> taskq(cmp);

// Build heap from existing array: O(n) — NOT O(n log n)!
vector<int> v = {4, 1, 7, 3, 9, 2};
// make_heap uses sift-down from n/2-1 to 0:
make_heap(v.begin(), v.end()); // O(n)
                               // push_heap / pop_heap (with vector) for manual control

// Heap layout in array: parent(i) = (i-1)/2
//                        left(i)  = 2*i+1
//                        right(i) = 2*i+2
// Array [9, 4, 7, 3, 1, 2] represents:
//           9
//         /   \
//        4     7
//       / \   /
//      3   1 2

What this lesson walks through

1. 01A binary heap is an array seen as a tree
2. 02push — append, then sift UP
3. 03pop — take the root, then sift DOWN
4. 04make_heap is O(n), not O(n log n)
5. 05Min-heap & custom comparator
6. 06Interview patterns

std::priority_queue is a binary max-heap stored in a contiguous array. The tree is implicit: for index i, parent = (i-1)/2, children = 2i+1 and 2i+2. The only rule is parent ≥ both children — it's NOT fully sorted.