Module 07: Heaps & Priority Queues — Mechanics, Top-K & Streams

Goal: Master array-backed binary heaps, $O(N)$ bottom-up heapification proofs, custom C++ STL comparators, Two-Heap architectures for dynamic medians, and K-way merging.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 06.

📑 Table of Contents

Under the Hood: Complete Binary Tree Array Representation
Min-Heap Implementation from Scratch in C++
Mathematical Proof: Why buildHeap Runs in $O(N)$
C++ std::priority_queue & Custom Comparators
Pattern 1: Top-K Elements with Size-Bound Min-Heap
Pattern 2: Two Heaps for Dynamic Median Maintenance
Pattern 3: K-Way Merge
5 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. Under the Hood: Complete Binary Tree Array Representation

A Binary Heap is a complete binary tree stored compactly in a contiguous array without pointers.

Tree Representation:                           Array Representation:
             [ 10 ]  (Index 0)                  Index: 0   1   2   3   4   5   6
            /      \                            Arr:  [10 |15 |30 |40 |50 |100|40]
        [ 15 ]    [ 30 ]  (Indices 1, 2)
        /    \    /    \
      [40]  [50] [100] [40] (Indices 3..6)

Index Math (0-Indexed Array)

For any element at index $i$:

Parent Index: $\lfloor (i - 1) / 2 \rfloor$
Left Child Index: $2i + 1$
Right Child Index: $2i + 2$

Heap Invariants

Min-Heap: For every node $i$ (except root), $\text{arr}[\text{parent}(i)] \le \text{arr}[i]$. Root is the absolute minimum.
Max-Heap: For every node $i$ (except root), $\text{arr}[\text{parent}(i)] \ge \text{arr}[i]$. Root is the absolute maximum.

2. Min-Heap Implementation from Scratch in C++

#include <vector>
#include <stdexcept>
#include <algorithm>

class MinHeap {
private:
    std::vector<int> heap;

    int parent(int i) { return (i - 1) / 2; }
    int leftChild(int i) { return 2 * i + 1; }
    int rightChild(int i) { return 2 * i + 2; }

    void siftUp(int i) {
        while (i > 0 && heap[parent(i)] > heap[i]) {
            std::swap(heap[parent(i)], heap[i]);
            i = parent(i);
        }
    }

    void siftDown(int i) {
        int minIndex = i;
        int left = leftChild(i);
        int right = rightChild(i);
        int n = heap.size();

        if (left < n && heap[left] < heap[minIndex]) minIndex = left;
        if (right < n && heap[right] < heap[minIndex]) minIndex = right;

        if (minIndex != i) {
            std::swap(heap[i], heap[minIndex]);
            siftDown(minIndex);
        }
    }

public:
    MinHeap() {}

    // O(N) Bottom-Up Heap Construction
    MinHeap(const std::vector<int>& arr) : heap(arr) {
        for (int i = (heap.size() / 2) - 1; i >= 0; --i) {
            siftDown(i);
        }
    }

    void push(int val) {
        heap.push_back(val);
        siftUp(heap.size() - 1); // O(log N)
    }

    int pop() {
        if (heap.empty()) throw std::out_of_range("Heap is empty");
        int rootVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0); // O(log N)
        return rootVal;
    }

    int peek() const {
        if (heap.empty()) throw std::out_of_range("Heap is empty");
        return heap[0]; // O(1)
    }

    size_t size() const { return heap.size(); }
    bool empty() const { return heap.empty(); }
};

3. Mathematical Proof: Why `buildHeap` Runs in $O(N)$

In bottom-up heapification, we run siftDown starting from the first non-leaf node index $\lfloor N/2 \rfloor - 1$ down to $0$.

Tree Levels and Heights:
Level 0 (Root, h = log N):      1 node   ──► Sift down cost: log N
Level 1 (h = log N - 1):        2 nodes  ──► Sift down cost: log N - 1
...
Level h (Height h):             N / 2^(h+1) nodes ──► Sift down cost: h
Level log N (Leaves, h = 0):    N / 2 nodes  ──► Sift down cost: 0

Total work $S$: $$S = \sum_{h=0}^{\lfloor \log N \rfloor} \frac{N}{2^{h+1}} \cdot h = \frac{N}{2} \sum_{h=0}^{\infty} \frac{h}{2^h}$$

Let $T = \sum_{h=0}^{\infty} \frac{h}{2^h} = \frac{0}{1} + \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \dots$
Multiply $T$ by $\frac{1}{2}$: $$\frac{1}{2} T = \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \dots$$ Subtract $\frac{1}{2} T$ from $T$: $$T - \frac{1}{2} T = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \dots = \frac{1/2}{1 - 1/2} = 1$$ $$\frac{1}{2} T = 1 \implies T = 2$$

Substitute $T = 2$ back into total work: $$S = \frac{N}{2} \cdot 2 = N = \Theta(N)$$

Conclusion: Building a heap bottom-up takes $O(N)$ time, whereas repeatedly calling push() takes $O(N \log N)$!

4. C++ `std::priority_queue` & Custom Comparators

4.1 Max-Heap (Default) vs Min-Heap

#include <queue>
#include <vector>

// 1. Default Max-Heap (largest on top)
std::priority_queue<int> maxHeap;

// 2. Standard Min-Heap (smallest on top)
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

4.2 Custom Comparator Struct (e.g. Points by Distance)

struct Point { int x, y; };

struct PointCompare {
    bool operator()(const Point& a, const Point& b) {
        // Return true if 'a' has LOWER priority than 'b' (for Min-Heap)
        return (a.x * a.x + a.y * a.y) > (b.x * b.x + b.y * b.y);
    }
};

std::priority_queue<Point, std::vector<Point>, PointCompare> minPointHeap;

5. Pattern 1: Top-K Elements with Size-Bound Min-Heap

To find the $K$ largest elements from a stream or array of size $N$:

Maintain a Min-Heap of size $K$.
For each incoming element, if heap size $< K$, push it.
If element $> \text{heap.top()}$, pop the min element and push the new element.
Total Time: $O(N \log K)$ — much faster than $O(N \log N)$ sorting when $K \ll N$.

// Template: Kth Largest Element
int findKthLargest(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) minHeap.pop();
    }
    return minHeap.top();
}

6. Pattern 2: Two Heaps for Dynamic Median Maintenance

Maintain two balanced heaps:

maxHeap: stores smaller half of numbers (root is largest of smaller half).
minHeap: stores larger half of numbers (root is smallest of larger half).

Smaller Half (Max-Heap)     │     Larger Half (Min-Heap)
[ 1, 3, 5, 7, (9) ]         │     [ (12), 15, 18, 20 ]
              ▲             │       ▲
              │             │       │
          maxHeap.top()     │   minHeap.top()

Median = maxHeap.top() (if odd count) OR (maxHeap.top() + minHeap.top()) / 2.0 (if even count)

7. Pattern 3: K-Way Merge

Merge $K$ sorted arrays/lists by inserting the head element of each list into a Min-Heap of size $K$. Each pop extracts the global minimum, and the next element from that specific list is pushed into the heap. Total Time: $O(N \log K)$.

8. 5 Practice Problems with Detailed Solutions

Problem 1: Find Median from Data Stream (LeetCode #295 - Hard)

Problem: Design a data structure that supports adding integer numbers from a data stream and finding the median of all elements in $O(1)$ time.

#include <queue>
#include <vector>

class MedianFinder {
private:
    std::priority_queue<int> maxHeap; // Lower half
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // Upper half

public:
    MedianFinder() {}

    void addNum(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        // Rebalance heaps so maxHeap has at most 1 more element than minHeap
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};
// addNum: O(log N)
// findMedian: O(1)
// Space: O(N)

Problem 2: Merge k Sorted Lists (LeetCode #23 - Hard)

Problem: Merge $K$ sorted linked lists and return it as one sorted list.

#include <vector>
#include <queue>

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

class SolutionMergeKLists {
private:
    struct CompareNodes {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val; // Min-Heap
        }
    };

public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        std::priority_queue<ListNode*, std::vector<ListNode*>, CompareNodes> pq;
        
        for (ListNode* head : lists) {
            if (head) pq.push(head);
        }
        
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (!pq.empty()) {
            ListNode* minNode = pq.top();
            pq.pop();
            
            tail->next = minNode;
            tail = tail->next;
            
            if (minNode->next) {
                pq.push(minNode->next);
            }
        }
        
        return dummy.next;
    }
};
// Time Complexity: O(N log K) where N = total nodes, K = number of lists
// Auxiliary Space: O(K) for priority queue

Problem 3: Top K Frequent Elements (LeetCode #347 - Medium)

Problem: Given an integer array nums and an integer k, return the k most frequent elements.

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

std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
    std::unordered_map<int, int> freqMap;
    for (int num : nums) freqMap[num]++;
    
    // Min-Heap storing pair: (frequency, value)
    typedef std::pair<int, int> Element;
    std::priority_queue<Element, std::vector<Element>, std::greater<Element>> minHeap;
    
    for (auto& entry : freqMap) {
        minHeap.push({entry.second, entry.first});
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    std::vector<int> result;
    result.reserve(k);
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    return result;
}
// Time Complexity: O(N log K)
// Space Complexity: O(N)

Problem 4: Task Scheduler (LeetCode #621 - Medium)

Problem: Given characters tasks representing CPU tasks and cooling interval n, return the least number of CPU intervals to finish all tasks.

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

int leastInterval(std::vector<char>& tasks, int n) {
    std::vector<int> freq(26, 0);
    for (char t : tasks) freq[t - 'a']++;
    
    std::priority_queue<int> maxHeap;
    for (int f : freq) {
        if (f > 0) maxHeap.push(f);
    }
    
    int time = 0;
    // Queue storing pair: (remaining_frequency, available_time)
    std::queue<std::pair<int, int>> coolDownQueue;
    
    while (!maxHeap.empty() || !coolDownQueue.empty()) {
        time++;
        
        if (!maxHeap.empty()) {
            int currentFreq = maxHeap.top() - 1;
            maxHeap.pop();
            if (currentFreq > 0) {
                coolDownQueue.push({currentFreq, time + n});
            }
        }
        
        if (!coolDownQueue.empty() && coolDownQueue.front().second == time) {
            maxHeap.push(coolDownQueue.front().first);
            coolDownQueue.pop();
        }
    }
    
    return time;
}
// Time Complexity: O(Total Tasks)
// Space Complexity: O(1) (fixed 26 letters)

Problem 5: K Closest Points to Origin (LeetCode #973 - Medium)

#include <vector>
#include <queue>

std::vector<std::vector<int>> kClosest(std::vector<std::vector<int>>& points, int k) {
    // Max-Heap of size K
    auto comp = [](const std::vector<int>& a, const std::vector<int>& b) {
        return (a[0]*a[0] + a[1]*a[1]) < (b[0]*b[0] + b[1]*b[1]);
    };
    std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, decltype(comp)> maxHeap(comp);
    
    for (const auto& pt : points) {
        maxHeap.push(pt);
        if (maxHeap.size() > k) maxHeap.pop();
    }
    
    std::vector<std::vector<int>> result;
    while (!maxHeap.empty()) {
        result.push_back(maxHeap.top());
        maxHeap.pop();
    }
    return result;
}
// Time Complexity: O(N log K)
// Space Complexity: O(K)

9. Top 10 FAANG Interview Questions

Q1: What is the difference between a Binary Heap and a Binary Search Tree (BST)?

Answer:

Ordering: In a BST, the left child is smaller and right child is larger than the parent (total ordering). In a Heap, both children are smaller (Max-Heap) or larger (Min-Heap) than parent (partial ordering, no relation between siblings).
Structure: Heap is strictly a Complete Binary Tree backed by a contiguous array with zero pointer overhead. BST requires explicit node pointers and is not guaranteed to be balanced unless AVL/Red-Black logic is added.
Search: Heap search is $O(N)$ (must inspect all nodes). BST search is $O(\log N)$.

Q2: Why is array indexing faster than pointer-based trees for heaps?

Answer: Array indexing computes child addresses with a single CPU instruction (2*i + 1 is (i << 1) + 1), avoiding pointer dereferencing and capitalizing on CPU cache lines.

Q3: How do you implement a D-ary Heap (e.g. 4-ary Heap)? What are its advantages?

Answer: In a D-ary heap, each node has $D$ children:

Parent: $\lfloor (i - 1) / D \rfloor$
$k$-th Child: $D \cdot i + k + 1$ (for $k = 0 \dots D-1$).
Advantage: Tree height decreases from $\log_2 N$ to $\log_D N$, speeding up siftUp / decreaseKey operations (used in Dijkstra's algorithm for dense graphs).

Q4: How does `std::make_heap` work under the hood?

Answer: It executes the $O(N)$ bottom-up siftDown algorithm directly in-place on a random-access iterator range [first, last).

Q5: What is QuickSelect, and when is it better than a Heap for Kth Largest Element?

Answer: QuickSelect uses the partition step of QuickSort to find the $K$-th element in $O(N)$ average time and $O(1)$ extra space, compared to $O(N \log K)$ for a heap. However, QuickSelect is $O(N^2)$ worst-case and modifies the input array in-place.

Q6: Can we decrease the key of an element in `std::priority_queue` in $O(\log N)$?

Answer: Standard std::priority_queue does not support decreaseKey because it does not expose element indices or iterators. Solution: Use an Indexed Priority Queue that maintains a separate unordered_map<Key, int> tracking each element's position inside the heap array.

Q7: What is a Fibonacci Heap, and where is it used?

Answer: A collection of trees with amortized $O(1)$ insert, $O(1)$ findMin, and $O(1)$ decreaseKey, and $O(\log N)$ deleteMin. Used in theoretical shortest path (Dijkstra runs in $O(E + V \log V)$), though in practice its high constant factor makes Binary/D-ary heaps faster for realistic graph sizes.

Q8: How do you find the $K$ smallest elements in a Min-Heap of size $N$ in $O(K \log K)$ time without modifying the original heap?

Answer: Use an auxiliary Min-Heap storing (value, index_in_original_heap).

Push (heap[0], 0) into auxiliary heap.
For $K$ iterations: Pop minimum (val, idx) from aux heap, output val, and push its children (heap[2*idx+1] and heap[2*idx+2]) into aux heap. Runs in $O(K \log K)$ independent of $N$!

Q9: Why is `siftDown` faster than `siftUp` during heap construction?

Answer: Most nodes in a binary tree reside near the bottom (leaves). siftDown does $0$ work on leaves and minimal work on majority nodes. siftUp does maximal work ($\log N$) on leaves, leading to $O(N \log N)$ total work.

Q10: How do you implement a Sliding Window Median?

Answer: Use Two Heaps with Lazy Deletion (hash map tracking counts of elements waiting to be purged from heaps), or use a balanced BST (std::multiset in C++ with an iterator tracking the median).

07-heaps-and-priority-queues.md