Heaps & Priority Queues

Chapter 12 · Part 3: TREES · Est. 26 min read

Chapter Goal: Master the heap data structure from internals to the three canonical interview patterns — Top-K, K-way Merge, and Two Heaps. The heap is the engine behind Dijkstra's, Huffman coding, median streams, and a broad family of greedy scheduling problems. Know it cold.

12.1 Heap Properties — Min-Heap vs. Max-Heap

What Is a Heap?

A heap is a complete binary tree (all levels filled left to right) satisfying the heap property:

Max-Heap: Every parent's value ≥ its children's values
          Root holds the MAXIMUM element

Min-Heap: Every parent's value ≤ its children's values
          Root holds the MINIMUM element

Max-Heap:              Min-Heap:
       90                     1
      /  \                   / \
    75    80                3   5
   / \   /  \              / \ / \
  40  55 65  70           6  4 8  9

Array Representation

A heap's complete binary tree structure maps perfectly to a 1-indexed array:

Array (1-indexed):  [_, 90, 75, 80, 40, 55, 65, 70]
                         1   2   3   4   5   6   7

For node at index i:
  Left child:   2 * i
  Right child:  2 * i + 1
  Parent:       i / 2

For 0-indexed array (C++ STL):
  Left child:   2 * i + 1
  Right child:  2 * i + 2
  Parent:       (i - 1) / 2

// Verify manually:
// Node 90 at index 1: left=75 at 2, right=80 at 3
// Node 75 at index 2: left=40 at 4, right=55 at 5   ✓
// Node 80 at index 3: left=65 at 6, right=70 at 7   ✓

Height of a Heap

A heap with n elements has height ⌊log₂n⌋. All operations that touch a single path (insert, extract) are O(log n).

12.2 Heap Operations — Internals & Complexity

Sift-Up (Bubble-Up) — Used After Insert

After inserting a new element at the end, restore the heap property by comparing it with its parent and swapping upward until the property holds.

// Max-heap sift-up (0-indexed array)
void siftUp(vector<int>& heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent] < heap[i]) {      // Max-heap: parent should be larger
            swap(heap[parent], heap[i]);
            i = parent;
        } else break;
    }
}
 
void heapInsert(vector<int>& heap, int val) {
    heap.push_back(val);                   // Add at end
    siftUp(heap, heap.size() - 1);        // Restore heap property
}
// Time: O(log n) — at most log n swaps along root-to-leaf path

Sift-Down (Bubble-Down) — Used After Extract

After removing the root, move the last element to the root position and sift it down until the heap property is restored.

// Max-heap sift-down (0-indexed array, heap size = n)
void siftDown(vector<int>& heap, int i, int n) {
    while (true) {
        int largest = i;
        int left  = 2 * i + 1;
        int right = 2 * i + 2;
 
        if (left  < n && heap[left]  > heap[largest]) largest = left;
        if (right < n && heap[right] > heap[largest]) largest = right;
 
        if (largest == i) break;           // Heap property satisfied
 
        swap(heap[i], heap[largest]);
        i = largest;
    }
}
 
int heapExtractMax(vector<int>& heap) {
    int maxVal = heap[0];
    heap[0] = heap.back();                 // Move last to root
    heap.pop_back();
    siftDown(heap, 0, heap.size());        // Restore heap property
    return maxVal;
}
// Time: O(log n)

Build Heap — O(n) Not O(n log n)

Calling insert n times costs O(n log n). But there's a smarter way: start from the last non-leaf node (index n/2 - 1) and sift-down each node.

// Build max-heap in-place in O(n) — Floyd's Algorithm
void buildHeap(vector<int>& arr) {
    int n = arr.size();
    // Start from last non-leaf, sift down each node
    for (int i = n/2 - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }
}
// Time: O(n)  ← NOT O(n log n)!
// Space: O(1)
 
/*
  WHY O(n)?
  At height h, there are at most ceil(n / 2^(h+1)) nodes.
  Sifting a node at height h costs O(h).
  Total = sum_{h=0}^{log n} ceil(n/2^(h+1)) * h
        = n * sum_{h=0}^{inf} h/2^(h+1)
        = n * 1  (geometric series sum)
        = O(n)
 
  Most nodes are near the bottom (height 0 or 1) and cost almost nothing.
  Only the root (height log n) pays the full log n cost — but there's only 1 root.
*/

Complete Operation Complexity Table

Operation	Time	Space	Notes
`peek` (top)	O(1)	O(1)	Read root without removing
`insert` (push)	O(log n)	O(1)	Sift up
`extractMin/Max` (pop)	O(log n)	O(1)	Sift down
`build heap`	O(n)	O(1)	Floyd's algorithm
`heapify n elements` one-by-one	O(n log n)	O(1)	Repeated insert
`search`	O(n)	O(1)	No BST property — must scan
`delete` arbitrary element	O(log n)	O(1)	Need index; decrease-key then extract

12.3 `std::priority_queue` — Complete Reference

Default Max-Heap

#include <queue>
 
priority_queue<int> maxPQ;   // Max-heap by default
 
maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(4);
maxPQ.push(1);
maxPQ.push(5);
 
cout << maxPQ.top();   // 5 — maximum element
maxPQ.pop();
cout << maxPQ.top();   // 4
 
cout << maxPQ.size();  // 4
cout << maxPQ.empty(); // false

Min-Heap Using `greater<T>`

priority_queue<int, vector<int>, greater<int>> minPQ;
 
minPQ.push(3); minPQ.push(1); minPQ.push(4);
cout << minPQ.top();   // 1 — minimum element

Min-Heap Using Lambda Comparator

auto cmp = [](int a, int b) { return a > b; };  // a > b means a has LOWER priority
priority_queue<int, vector<int>, decltype(cmp)> minPQ(cmp);

Priority Queue with Pairs

// Default: max-heap by first element, then second
priority_queue<pair<int,int>> pq;
pq.push({3, 10});
pq.push({5, 2});
pq.push({5, 8});
cout << pq.top().first;   // 5 (max first element)
 
// Min-heap by first element (Dijkstra's):
priority_queue<pair<int,int>,
               vector<pair<int,int>>,
               greater<pair<int,int>>> dijkstraPQ;
dijkstraPQ.push({0, src});   // {distance, node}

Custom Struct in Priority Queue

struct Task {
    int priority, id;
    bool operator<(const Task& other) const {
        return priority < other.priority;   // Max-heap: higher priority on top
    }
};
priority_queue<Task> taskPQ;
taskPQ.push({5, 1});
taskPQ.push({3, 2});
cout << taskPQ.top().id;   // 1 (priority 5 is highest)
 
// Using lambda (avoid modifying struct):
auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority;   // Max-heap
};
priority_queue<Task, vector<Task>, decltype(cmp)> taskPQ2(cmp);

Build Priority Queue from Existing Vector — O(n)

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
 
// O(n) using range constructor — internally uses make_heap
priority_queue<int> pq(v.begin(), v.end());
 
// O(n log n) using repeated push — avoid this!
priority_queue<int> pqSlow;
for (int x : v) pqSlow.push(x);

Key fact: priority_queue's range constructor calls make_heap internally, which is O(n). Always prefer this over n individual pushes when initializing from an existing collection.

The Comparator Direction Rule — Critical

sort comparator:             cmp(a, b) = true  → a comes BEFORE b
priority_queue comparator:   cmp(a, b) = true  → b has HIGHER priority than a
                             (a is "less than" b, so b is closer to the top)

To get a MAX-heap: cmp = less<T>     → larger values have higher priority
To get a MIN-heap: cmp = greater<T>  → smaller values have higher priority

// Mnemonic: for MIN-heap, the comparator RETURNS > (greater than)
auto minCmp = [](int a, int b) { return a > b; };   // MIN-heap
// Reads: "a is deprioritized when a > b" → smaller b gets higher priority

12.4 `make_heap`, `push_heap`, `pop_heap` — STL Algorithms

These algorithms operate on a random-access range (vector) that satisfies the heap property.

#include <algorithm>
 
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
 
// Build max-heap in-place: O(n)
make_heap(v.begin(), v.end());
// v is now a valid max-heap (e.g., [9,6,4,1,5,1,2,3])
cout << v.front();   // 9 — maximum (front of vector = heap root)
 
// Add element and maintain heap property: O(log n)
v.push_back(7);
push_heap(v.begin(), v.end());   // Sifts 7 up to correct position
cout << v.front();               // Still 9
 
// Remove max element: O(log n)
pop_heap(v.begin(), v.end());    // Moves max to back, heapifies rest
int maxVal = v.back();           // 9
v.pop_back();                    // Remove from back
 
// Min-heap variant
make_heap(v.begin(), v.end(), greater<int>());
push_heap(v.begin(), v.end(), greater<int>());
pop_heap(v.begin(), v.end(), greater<int>());

When to use heap algorithms vs. priority_queue:

Use priority_queue when you only need push/pop/top.
Use make_heap/push_heap/pop_heap when you need direct access to all elements (since priority_queue doesn't expose its underlying container).

12.5 Heap Sort

Heap sort runs in O(n log n) guaranteed, uses O(1) extra space, but is NOT stable. In practice, it's slower than Introsort (std::sort) due to poor cache performance.

void heapSort(vector<int>& arr) {
    int n = arr.size();
 
    // Phase 1: Build max-heap — O(n)
    for (int i = n/2 - 1; i >= 0; i--)
        siftDown(arr, i, n);
 
    // Phase 2: Extract elements one by one — O(n log n)
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);      // Move current max to end
        siftDown(arr, 0, i);       // Restore heap on arr[0..i-1]
    }
    // arr is now sorted ascending
}
// Time: O(n log n) guaranteed (no worst case like quicksort)
// Space: O(1) — in-place
// Stable: NO
 
/*
  arr = [3, 1, 4, 1, 5]
  Phase 1 build-heap: [5, 1, 4, 1, 3] (valid max-heap)
  i=4: swap 5,3 → [3,1,4,1,|5]. siftDown → [4,1,3,1,|5]
  i=3: swap 4,1 → [1,1,3,|4,5]. siftDown → [3,1,1,|4,5]
  i=2: swap 3,1 → [1,1,|3,4,5]. siftDown → [1,1,|3,4,5]
  i=1: swap 1,1 → [1,|1,3,4,5]. Already sorted.
  Result: [1,1,3,4,5] ✓
*/

12.6 Top-K Elements Pattern

The Core Insight

Goal	Heap Type	Why
K LARGEST elements	Min-heap of size k	Min-heap top = smallest of the k largest. Discard smaller arrivals.
K SMALLEST elements	Max-heap of size k	Max-heap top = largest of the k smallest. Discard larger arrivals.
Kth LARGEST element	Min-heap of size k	Top = kth largest when heap has k elements.
Kth SMALLEST element	Max-heap of size k	Top = kth smallest when heap has k elements.

K Largest using min-heap of size k:
  Current heap: [3, 5, 7] (min-heap, k=3)
  New element 8: 8 > heap.top()=3 → pop 3, push 8 → [5, 7, 8]
  New element 2: 2 < heap.top()=5 → 2 cannot be in top 3, discard
  Final top-3: [5, 7, 8] ✓

Template: K Largest Elements

vector<int> topKLargest(vector<int>& nums, int k) {
    // Min-heap of size k — top = smallest of the k largest so far
    priority_queue<int, vector<int>, greater<int>> minPQ;
 
    for (int x : nums) {
        minPQ.push(x);
        if ((int)minPQ.size() > k) minPQ.pop();  // Evict the smallest
    }
 
    vector<int> result;
    while (!minPQ.empty()) {
        result.push_back(minPQ.top());
        minPQ.pop();
    }
    return result;   // In ascending order; reverse for descending
}
// Time: O(n log k), Space: O(k)

Template: K Smallest Elements

vector<int> topKSmallest(vector<int>& nums, int k) {
    // Max-heap of size k — top = largest of the k smallest so far
    priority_queue<int> maxPQ;
 
    for (int x : nums) {
        maxPQ.push(x);
        if ((int)maxPQ.size() > k) maxPQ.pop();  // Evict the largest
    }
 
    vector<int> result;
    while (!maxPQ.empty()) {
        result.push_back(maxPQ.top());
        maxPQ.pop();
    }
    return result;
}
// Time: O(n log k), Space: O(k)

Kth Largest: Heap vs. Quickselect

Approach	Time (avg)	Time (worst)	Space	Use When
Sort	O(n log n)	O(n log n)	O(1)	Simple, not optimal
Min-heap size k	O(n log k)	O(n log k)	O(k)	Streaming input, k << n
Quickselect	O(n)	O(n²)	O(1)	Static array, best average
Introselect	O(n)	O(n)	O(1)	Guaranteed, complex

// Quickselect: O(n) average, in-place, no extra space
int quickselect(vector<int>& nums, int lo, int hi, int k) {
    if (lo == hi) return nums[lo];
 
    // Partition around pivot
    int pivot = nums[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (nums[j] >= pivot) swap(nums[i++], nums[j]);  // ≥ pivot moves left
    }
    swap(nums[i], nums[hi]);   // Place pivot
 
    if (i == k) return nums[i];
    else if (i < k) return quickselect(nums, i+1, hi, k);
    else            return quickselect(nums, lo, i-1, k);
}
 
int findKthLargest(vector<int>& nums, int k) {
    return quickselect(nums, 0, nums.size()-1, k-1);
}
// Time: O(n) average, O(n²) worst | Space: O(log n) recursion

12.7 K-way Merge Pattern

Merge k sorted sequences into one sorted sequence in O(N log k) where N is the total number of elements.

Template: Merge K Sorted Arrays

// Each element in heap: {value, array_index, element_index}
vector<int> mergeKSorted(vector<vector<int>>& arrays) {
    // Min-heap: {value, array_idx, elem_idx}
    using T = tuple<int,int,int>;
    priority_queue<T, vector<T>, greater<T>> minPQ;
 
    // Initialize with first element of each array
    for (int i = 0; i < (int)arrays.size(); i++) {
        if (!arrays[i].empty()) {
            minPQ.push({arrays[i][0], i, 0});
        }
    }
 
    vector<int> result;
    while (!minPQ.empty()) {
        auto [val, arrIdx, elemIdx] = minPQ.top(); minPQ.pop();
        result.push_back(val);
 
        // Push next element from the same array
        if (elemIdx + 1 < (int)arrays[arrIdx].size()) {
            minPQ.push({arrays[arrIdx][elemIdx+1], arrIdx, elemIdx+1});
        }
    }
    return result;
}
// Time: O(N log k), Space: O(k)

Template: Merge K Sorted Linked Lists (LC 23)

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
 
    for (ListNode* head : lists) if (head) pq.push(head);
 
    ListNode dummy(0); ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node; tail = tail->next;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}
// Time: O(N log k), Space: O(k)

Finding the Kth Smallest in a Sorted Matrix (LC 378)

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    // Min-heap: {value, row, col}
    priority_queue<tuple<int,int,int>,
                   vector<tuple<int,int,int>>,
                   greater<>> minPQ;
 
    // Push first element of each row (all sorted)
    for (int r = 0; r < n; r++) minPQ.push({matrix[r][0], r, 0});
 
    int result = 0;
    for (int i = 0; i < k; i++) {
        auto [val, r, c] = minPQ.top(); minPQ.pop();
        result = val;
        if (c + 1 < n) minPQ.push({matrix[r][c+1], r, c+1});
    }
    return result;
}
// Time: O(k log n), Space: O(n)

12.8 Two Heaps Pattern — Median of Data Stream

The Problem

Maintain a data structure that supports:

Adding a number in O(log n)
Querying the median in O(1)

The Two-Heap Design

Maintain two heaps:

maxHeap (lower half): Max-heap containing the smaller half of numbers
minHeap (upper half): Min-heap containing the larger half of numbers

Invariant:

Every element in maxHeap ≤ every element in minHeap
|maxHeap.size() - minHeap.size()| ≤ 1 (sizes differ by at most 1)

Median:

If both heaps have equal size: (maxHeap.top() + minHeap.top()) / 2.0
If maxHeap is larger: maxHeap.top()
If minHeap is larger: minHeap.top()

Numbers: [1, 7, 3, 8, 2, 9, 5]
After each insertion:

Add 1:  maxH=[1]       minH=[]       median = 1.0
Add 7:  maxH=[1]       minH=[7]      median = (1+7)/2 = 4.0
Add 3:  maxH=[3,1]     minH=[7]      median = 3.0
Add 8:  maxH=[3,1]     minH=[7,8]    median = (3+7)/2 = 5.0
Add 2:  maxH=[3,2,1]   minH=[7,8]    median = 3.0
Add 9:  maxH=[3,2,1]   minH=[7,8,9]  median = (3+7)/2 = 5.0
Add 5:  maxH=[5,3,2,1] minH=[7,8,9]  median = 5.0

class MedianFinder {
    priority_queue<int>                             maxH;  // Lower half max-heap
    priority_queue<int,vector<int>,greater<int>>    minH;  // Upper half min-heap
 
public:
    void addNum(int num) {
        // Step 1: Push to maxH first (always)
        maxH.push(num);
 
        // Step 2: Maintain invariant: maxH.top() <= minH.top()
        if (!minH.empty() && maxH.top() > minH.top()) {
            minH.push(maxH.top()); maxH.pop();
        }
 
        // Step 3: Balance sizes: maxH can be at most 1 larger than minH
        if ((int)maxH.size() > (int)minH.size() + 1) {
            minH.push(maxH.top()); maxH.pop();
        } else if ((int)minH.size() > (int)maxH.size()) {
            maxH.push(minH.top()); minH.pop();
        }
    }
 
    double findMedian() {
        if (maxH.size() > minH.size()) return maxH.top();
        return (maxH.top() + minH.top()) / 2.0;
    }
};
// addNum: O(log n), findMedian: O(1)
 
/*
  Add 3: maxH=[3], minH=[]                  (balanced)
  Add 7: maxH=[3], push 7 → maxH=[7,3]
         maxH.top()=7 > minH empty? No. 
         maxH.size()=2 > minH.size()+1=1 → move 7 to minH
         maxH=[3], minH=[7]                 (balanced)
  Add 1: maxH=[3], push 1 → maxH=[3,1]
         maxH.top()=3 < minH.top()=7 ✓
         Sizes: maxH=2, minH=1. 2 > 1+1? No. ✓
         maxH=[3,1], minH=[7]               median=3.0
*/

Variation: Sliding Window Median (LC 480)

// Two multisets instead of heaps (for O(log n) arbitrary deletion)
class SlidingMedian {
    multiset<int> lower, upper;  // lower=max half, upper=min half
 
    void balance() {
        while (lower.size() > upper.size() + 1) {
            upper.insert(*lower.rbegin());
            lower.erase(lower.find(*lower.rbegin()));
        }
        while (upper.size() > lower.size()) {
            lower.insert(*upper.begin());
            upper.erase(upper.begin());
        }
    }
 
public:
    void add(int x) {
        if (lower.empty() || x <= *lower.rbegin()) lower.insert(x);
        else upper.insert(x);
        balance();
    }
 
    void remove(int x) {
        if (lower.count(x)) lower.erase(lower.find(x));
        else upper.erase(upper.find(x));
        balance();
    }
 
    double getMedian() {
        if (lower.size() > upper.size()) return *lower.rbegin();
        return (*lower.rbegin() + *upper.begin()) / 2.0;
    }
};

12.9 Sample Problems

Problem 1 — Kth Largest Element in an Array (Medium) — LC 215

int findKthLargest(vector<int>& nums, int k) {
    // Min-heap of size k: top = kth largest
    priority_queue<int, vector<int>, greater<int>> minPQ;
    for (int x : nums) {
        minPQ.push(x);
        if ((int)minPQ.size() > k) minPQ.pop();
    }
    return minPQ.top();
}
// Time: O(n log k), Space: O(k)

Problem 2 — Kth Largest Element in a Stream (Easy) — LC 703

class KthLargest {
    priority_queue<int, vector<int>, greater<int>> minPQ;
    int k;
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }
    int add(int val) {
        minPQ.push(val);
        if ((int)minPQ.size() > k) minPQ.pop();
        return minPQ.top();
    }
};
// add: O(log k), Space: O(k)

Problem 3 — Find Median from Data Stream (Hard) — LC 295

class MedianFinder {
    priority_queue<int> maxH;
    priority_queue<int,vector<int>,greater<int>> minH;
public:
    void addNum(int num) {
        maxH.push(num);
        if (!minH.empty() && maxH.top() > minH.top()) {
            minH.push(maxH.top()); maxH.pop();
        }
        if ((int)maxH.size() > (int)minH.size()+1) {
            minH.push(maxH.top()); maxH.pop();
        } else if ((int)minH.size() > (int)maxH.size()) {
            maxH.push(minH.top()); minH.pop();
        }
    }
    double findMedian() {
        if (maxH.size() > minH.size()) return maxH.top();
        return (maxH.top() + minH.top()) / 2.0;
    }
};
// addNum: O(log n), findMedian: O(1)

Problem 4 — K Closest Points to Origin (Medium) — LC 973

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    // Max-heap by distance squared — keep k smallest distances
    auto dist2 = [](const vector<int>& p) {
        return p[0]*p[0] + p[1]*p[1];
    };
    auto cmp = [&](const vector<int>& a, const vector<int>& b) {
        return dist2(a) < dist2(b);   // Max-heap: larger distance on top
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> maxPQ(cmp);
 
    for (auto& p : points) {
        maxPQ.push(p);
        if ((int)maxPQ.size() > k) maxPQ.pop();
    }
 
    vector<vector<int>> result;
    while (!maxPQ.empty()) {
        result.push_back(maxPQ.top());
        maxPQ.pop();
    }
    return result;
}
// Time: O(n log k), Space: O(k)

Problem 5 — Task Scheduler (Medium) — LC 621

Given tasks and a cooldown n, find the minimum time to finish all tasks.

Key insight: Greedily always execute the most frequent remaining task. If no valid task exists, idle. Use a max-heap by remaining count.

int leastInterval(vector<char>& tasks, int n) {
    int freq[26] = {};
    for (char t : tasks) freq[t-'A']++;
 
    priority_queue<int> maxPQ;
    for (int f : freq) if (f > 0) maxPQ.push(f);
 
    int time = 0;
    while (!maxPQ.empty()) {
        vector<int> temp;
        int cycle = n + 1;   // Process up to n+1 tasks per cycle
 
        // Execute up to n+1 tasks (most frequent first)
        while (cycle-- > 0 && !maxPQ.empty()) {
            int f = maxPQ.top(); maxPQ.pop();
            if (f > 1) temp.push_back(f - 1);
            time++;
        }
 
        for (int f : temp) maxPQ.push(f);
 
        // If heap not empty, we might need to idle to fill the cycle
        if (!maxPQ.empty()) time += cycle + 1;  // cycle is negative if we used full window
    }
    // Note: if maxPQ is empty after processing, no idle needed
    return time;
}
// Time: O(n * T) where T = number of unique tasks (bounded by 26)
// Space: O(1)
 
// Cleaner mathematical solution:
int leastInterval_math(vector<char>& tasks, int n) {
    int freq[26] = {};
    for (char t : tasks) freq[t-'A']++;
    int maxFreq = *max_element(freq, freq+26);
    int maxCount = count(freq, freq+26, maxFreq);
    // Slots needed: (maxFreq-1)*(n+1) + maxCount
    // But must be at least tasks.size() if tasks fill every slot
    return max((int)tasks.size(), (maxFreq-1)*(n+1) + maxCount);
}

Problem 6 — Reorganize String (Medium) — LC 767

Rearrange string so no two adjacent characters are the same.

string reorganizeString(string s) {
    int freq[26] = {};
    for (char c : s) freq[c-'a']++;
 
    // Max-heap by character frequency
    priority_queue<pair<int,char>> maxPQ;
    for (int i = 0; i < 26; i++)
        if (freq[i] > 0) maxPQ.push({freq[i], 'a'+i});
 
    string result;
    while (maxPQ.size() >= 2) {
        // Take the two most frequent characters
        auto [f1, c1] = maxPQ.top(); maxPQ.pop();
        auto [f2, c2] = maxPQ.top(); maxPQ.pop();
        result += c1; result += c2;
        if (f1 - 1 > 0) maxPQ.push({f1-1, c1});
        if (f2 - 1 > 0) maxPQ.push({f2-1, c2});
    }
    if (!maxPQ.empty()) {
        auto [f, c] = maxPQ.top();
        if (f > 1) return "";   // Impossible
        result += c;
    }
    return result;
}
// Time: O(n log 26) = O(n), Space: O(26) = O(1)

Problem 7 — Meeting Rooms II (Medium) — LC 253

Find the minimum number of conference rooms required.

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());  // Sort by start time
 
    // Min-heap of end times: tells us when the earliest room becomes free
    priority_queue<int, vector<int>, greater<int>> endTimes;
 
    for (auto& interval : intervals) {
        int start = interval[0], end = interval[1];
 
        // If earliest-ending room is free before this meeting starts, reuse it
        if (!endTimes.empty() && endTimes.top() <= start) {
            endTimes.pop();   // Reuse this room
        }
        endTimes.push(end);  // Assign room (new or reused) with this meeting's end time
    }
    return endTimes.size();  // Number of rooms in use
}
// Time: O(n log n), Space: O(n)

Problem 8 — Minimum Cost to Connect Sticks (Medium) — LC 1167

Connect sticks with minimum cost (cost = sum of two sticks being combined).

long long connectSticks(vector<int>& sticks) {
    priority_queue<long long, vector<long long>, greater<long long>> minPQ(
        sticks.begin(), sticks.end());
 
    long long totalCost = 0;
    while (minPQ.size() > 1) {
        long long a = minPQ.top(); minPQ.pop();
        long long b = minPQ.top(); minPQ.pop();
        totalCost += a + b;
        minPQ.push(a + b);
    }
    return totalCost;
}
// Time: O(n log n), Space: O(n)
// Greedy: always combine the two smallest sticks first (Huffman coding basis)

Problem 9 — Kth Smallest in Sorted Matrix (Medium) — LC 378

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
    for (int r = 0; r < n; r++) pq.push({matrix[r][0], r, 0});
 
    int result = 0;
    for (int i = 0; i < k; i++) {
        auto [val, r, c] = pq.top(); pq.pop();
        result = val;
        if (c+1 < n) pq.push({matrix[r][c+1], r, c+1});
    }
    return result;
}
// Time: O(k log n), Space: O(n)

Problem 10 — IPO (Hard) — LC 502

Pick at most k projects to maximize capital. Each project needs minimum capital and gives a profit.

Key insight: Two-heap approach — sort projects by capital. At each step, unlock all affordable projects into a max-heap of profits. Pick the most profitable.

int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    int n = profits.size();
    // Sort by minimum capital required
    vector<pair<int,int>> projects(n);
    for (int i = 0; i < n; i++) projects[i] = {capital[i], profits[i]};
    sort(projects.begin(), projects.end());
 
    priority_queue<int> maxProfits;  // Available projects' profits (max-heap)
    int idx = 0;
 
    for (int round = 0; round < k; round++) {
        // Unlock all projects we can now afford
        while (idx < n && projects[idx].first <= w) {
            maxProfits.push(projects[idx++].second);
        }
        if (maxProfits.empty()) break;   // No affordable projects
        w += maxProfits.top(); maxProfits.pop();
    }
    return w;
}
// Time: O(n log n + k log n), Space: O(n)

Problem 11 — Top K Frequent Elements (Medium) — LC 347

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    for (int x : nums) cnt[x]++;
 
    // Min-heap by frequency — keep top k
    auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
        return a.second > b.second;   // Min-heap by freq
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> minPQ(cmp);
 
    for (auto& [val, freq] : cnt) {
        minPQ.push({val, freq});
        if ((int)minPQ.size() > k) minPQ.pop();
    }
 
    vector<int> result;
    while (!minPQ.empty()) {
        result.push_back(minPQ.top().first);
        minPQ.pop();
    }
    return result;
}
// Time: O(n log k), Space: O(n + k)

Problem 12 — Ugly Number II (Medium) — LC 264

Find the nth "ugly number" (whose only prime factors are 2, 3, or 5).

int nthUglyNumber(int n) {
    priority_queue<long long, vector<long long>, greater<long long>> minPQ;
    unordered_set<long long> seen;
    minPQ.push(1); seen.insert(1);
 
    long long curr = 1;
    for (int i = 0; i < n; i++) {
        curr = minPQ.top(); minPQ.pop();
        for (long long factor : {2LL, 3LL, 5LL}) {
            long long next = curr * factor;
            if (!seen.count(next)) {
                seen.insert(next);
                minPQ.push(next);
            }
        }
    }
    return (int)curr;
}
// Time: O(n log n), Space: O(n)
 
// DP approach: O(n) time, O(n) space (optimal)
int nthUglyNumber_DP(int n) {
    vector<long long> dp(n);
    dp[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
 
    for (int i = 1; i < n; i++) {
        long long next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
        dp[i] = min({next2, next3, next5});
        if (dp[i] == next2) i2++;
        if (dp[i] == next3) i3++;
        if (dp[i] == next5) i5++;
    }
    return (int)dp[n-1];
}

12.10 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Kth Largest Element in an Array	Medium	Min-heap size k / Quickselect	LC 215
2	K Closest Points to Origin	Medium	Max-heap size k	LC 973
3	Top K Frequent Elements	Medium	Freq map + min-heap size k	LC 347
4	Task Scheduler	Medium	Max-heap greedy + math	LC 621
5	Meeting Rooms II	Medium	Min-heap of end times	LC 253
6	Kth Smallest in Sorted Matrix	Medium	K-way merge min-heap	LC 378
7	Find Median from Data Stream	Hard	Two heaps (max + min)	LC 295
8	IPO	Hard	Two-heap greedy	LC 502

Suggested order: #1 (Kth Largest) — the template. Then #2 and #3 (Top-K variants). Then #5 (Meeting Rooms) — classic scheduling with min-heap of end times. Then #6 (K-way merge pattern). #4 and #8 are harder greedy problems that combine heap with sorting. Save #7 (Median Stream) for last — it is the definitive Two-Heaps problem and should be solved cold from memory.