C++ In Practice - Priority Queues

Heap / Priority Queue (C++11 Deep Dive)

C++11 provides a robust, highly optimized standard library container: std::priority_queue. Additionally, the STL exposes low-level heap algorithms (std::make_heap, std::push_heap, std::pop_heap) if you need to treat a raw vector as a heap.

C++11 Architecture & std::priority_queue

Under the Hood:

• Container Adaptor: std::priority_queue is not a container itself; it wraps a sequence container (default: std::vector).
• Structure: It maintains the heap property (Max-Heap by default) using the underlying container's Random Access Iterators.
• Memory: Contiguous memory block. Cache-friendly.
• Complexity:
  • push(): O(log N) - push_back then swim (bubble up).
  • pop(): O(log N) - swap(root, last), pop_back, then sink (bubble down).
  • top(): O(1).

Default Behavior (Max-Heap):

std::priority_queue<int> pq; // Max-Heap (Largest on top)

Min-Heap Declaration:

// Type, Underlying Container, Comparator
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

---

1. Top K Frequent Elements

Pattern: HashMap + Min-Heap. Complexity: Time O(N log K) | Space O(N).

C++11 Detail: We store pair<count, value> in the heap. The comparator std::greater compares pairs lexicographically (first element, then second). This correctly prioritizes by count.

#include <vector>
#include <unordered_map>
#include <queue>

std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
    // 1. Count frequencies O(N)
    std::unordered_map<int, int> counts;
    for (int num : nums) {
        counts[num]++;
    }

    // 2. Min-Heap O(N log K)
    // We want to KEEP the K largest, so we use a Min-Heap to evict the smallest.
    // Pair: <Frequency, Value>
    using Item = std::pair<int, int>;
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> minHeap;

    for (const auto& entry : counts) {
        minHeap.push({entry.second, entry.first});
        if (minHeap.size() > k) {
            minHeap.pop(); // Remove the element with the smallest frequency
        }
    }

    // 3. Extract O(K)
    std::vector<int> result;
    result.reserve(k);
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    return result;
}

---

2. Kth Largest Element (QuickSelect vs. Heap)

Problem: Find the Kth largest element.

Approach A: Min-Heap (O(N log K)) Maintain a Min-Heap of size K. The root is the Kth largest.

int findKthLargestHeap(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int n : nums) {
        minHeap.push(n);
        if (minHeap.size() > k) minHeap.pop();
    }
    return minHeap.top();
}

Approach B: QuickSelect (O(N) Average, O(N^2) Worst) C++11 provides std::nth_element. This is a highly optimized QuickSelect implementation. It partially sorts the range such that the element at nth position is the one that would be there if the range were fully sorted.

#include <vector>
#include <algorithm>
#include <functional> // for std::greater

int findKthLargestQuickSelect(std::vector<int>& nums, int k) {
    // We want the Kth largest.
    // In a sorted (descending) array, this is at index k-1.
    // std::nth_element rearranges elements such that:
    // [0, n) contains elements >= nums[n]
    // nums[n] is the nth largest
    // [n+1, end) contains elements <= nums[n]
    
    auto target = nums.begin() + k - 1;
    std::nth_element(nums.begin(), target, nums.end(), std::greater<int>());
    
    return *target;
}

---

3. Merge K Sorted Lists

Pattern: Min-Heap stores iterators. Complexity: Time O(N log K) where N is total elements, K is number of lists.

C++11 Implementation: We need a custom comparator struct because we are storing ListNode*.

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct CompareNode {
    // Min-Heap requires 'greater' logic (returns true if a > b)
    bool operator()(ListNode* const& p1, ListNode* const& p2) {
        return p1->val > p2->val;
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, CompareNode> minHeap;

    // Initialize heap
    for (ListNode* list : lists) {
        if (list) minHeap.push(list);
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!minHeap.empty()) {
        ListNode* smallest = minHeap.top();
        minHeap.pop();

        tail->next = smallest;
        tail = tail->next;

        if (smallest->next) {
            minHeap.push(smallest->next);
        }
    }

    return dummy.next;
}

---

4. Find Median from Data Stream

Pattern: Two Heaps (Max-Heap for lower half, Min-Heap for upper half). Complexity: addNum: O(log N), findMedian: O(1).

Visual: [Small Elements | MaxHeap] <==> [MinHeap | Large Elements]

#include <queue>
#include <vector>
#include <functional>

class MedianFinder {
    std::priority_queue<int> lowerHalf; // Max-Heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> upperHalf; // Min-Heap

public:
    void addNum(int num) {
        // 1. Add to lower half
        lowerHalf.push(num);

        // 2. Balance: Move largest of lower to upper
        upperHalf.push(lowerHalf.top());
        lowerHalf.pop();

        // 3. Maintain Size Property: Lower half size >= Upper half size
        if (lowerHalf.size() < upperHalf.size()) {
            lowerHalf.push(upperHalf.top());
            upperHalf.pop();
        }
    }

    double findMedian() {
        if (lowerHalf.size() > upperHalf.size()) {
            return lowerHalf.top();
        }
        return (lowerHalf.top() + upperHalf.top()) * 0.5;
    }
};

---

5. Advanced: make_heap, push_heap, pop_heap

Sometimes you want to manipulate a vector as a heap without the wrapper of priority_queue (e.g., to access arbitrary elements or sort in-place).

#include <vector>
#include <algorithm>
#include <iostream>

void heapAlgorithms() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};

    // 1. O(N) Build Heap
    std::make_heap(v.begin(), v.end()); 
    // v is now a Max-Heap structure: {9, 5, 4, 1, 1, 3}

    // 2. Push Heap O(log N)
    v.push_back(6); 
    std::push_heap(v.begin(), v.end()); 
    // Moves the last element into heap position

    // 3. Pop Heap O(log N)
    std::pop_heap(v.begin(), v.end()); 
    // Moves root (max) to the end of vector, then re-heapifies the rest.
    int maxVal = v.back(); 
    v.pop_back(); // Remove it physically
    
    // 4. Sort Heap O(N log N)
    // Converts a heap into a sorted array (in-place)
    std::sort_heap(v.begin(), v.end());
}

Summary of Heap Patterns

Scenario	C++ Container/Algo	Complexity	Key Insight
Top K Largest	priority_queue<T, vector<T>, greater<T>>	O(N log K)	Use Min-Heap of size K.
Top K Smallest	priority_queue<T> (Default Max)	O(N log K)	Use Max-Heap of size K.
Find Kth Element	std::nth_element	O(N)	Pivot-based partitioning (QuickSelect).
Merge Streams	priority_queue with Custom Comparator	O(N log K)	Keep one active element per stream.
Rolling Median	Max-Heap + Min-Heap	O(log N)	Balance elements between two halves.