Priority Queue Patterns: Running Median (Two Heaps), K-Way Merge & Top-K

Three Canonical Systems Patterns Built on Priority Queues

1. Dual Opposing Heaps for Streaming Order Statistics (Median & $p$-th Quantile)

To maintain the exact median of a dynamic stream of $N$ numbers, partition the elements into two halves:

• lo (Max-Heap): Stores the smaller $\lceil N/2 \rceil$ elements, exposing the largest element of the lower half at lo.top().
• hi (Min-Heap): Stores the larger $\lfloor N/2 \rfloor$ elements, exposing the smallest element of the upper half at hi.top().

Lazy Deletion for Sliding Window Median: What if elements also expire as a window of width $W$ slides across the stream? Deleting an arbitrary expired element from an unindexed heap takes $O(W)$, but we can achieve $O(\log W)$ amortized time using lazy hash-map deletion: maintain an int balance counter of *valid* elements in lo minus hi, record expired values in delayed[val]++, and only physically pop elements when they bubble up to lo.top() or hi.top()!

2. Streaming Top-$K$ Elements: Opposing Sign Min-Heap vs Quickselect

To find the $K$ largest elements in a stream of $N \gg K$ items, do not use a Max-Heap of size $N$ ($O(N)$ memory). Instead, maintain a Min-Heap of fixed capacity $K$ storing the $K$ largest elements seen so far. The root minHeap.top() acts as the gatekeeper threshold (the $K$-th largest element): any incoming $x \le \text{minHeap.top()}$ is discarded in $O(1)$ time without touching the heap!

3. External $K$-Way Merge with Loser Trees (Tournament Trees)

Merging $K$ sorted runs totaling $N$ elements with a standard binary Min-Heap of size $K$ takes $O(N \log_2 K)$ time, performing $2 \log_2 K$ key comparisons per emitted record. In RocksDB, LevelDB, and Apache Arrow, engineers replace the binary heap with Knuth's Tournament Loser Tree: internal nodes store the loser of each match while the winner propagates up, reducing comparisons per element by $50\%$ to strictly $\log_2 K$!

Implementation: Two-Heap Streaming Median & $K$-Way Merge

// C++20: Overflow-Safe Running Median Finder via Dual Opposing Heaps
#include <queue>
#include <vector>
#include <functional>

class MedianFinder {
    std::priority_queue<long long> lo; // Max-Heap for lower half
    std::priority_queue<long long, std::vector<long long>, std::greater<>> hi; // Min-Heap for upper half

public:
    void addNum(long long x) {
        lo.push(x);
        hi.push(lo.top());
        lo.pop();
        if (hi.size() > lo.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian() const {
        if (lo.size() > hi.size()) {
            return static_cast<double>(lo.top());
        }
        // Overflow-safe midpoint calculation
        return static_cast<double>(lo.top()) + ( static_cast<double>(hi.top()) - static_cast<double>(lo.top()) ) * 0.5;
    }
};