Mastering Heaps & Priority Queues

Heaps (or Priority Queues) are specialized tree-based data structures that satisfy the heap property: in a min-heap, the parent key is always smaller than or equal to child keys. This allows fetching the minimum element in O(1) time.

Tracking Top-K Frequent Elements

When dealing with data streams where we continually push items and need to retrieve the top-K largest or most frequent, a min-heap of size K is highly optimal. By keeping only K elements in the heap, we perform insertions in O(log K) rather than sorting the entire list.

// Simulating heap push and pop for top K elements
class MinHeap {
    constructor() { this.data = []; }
    push(val) {
        this.data.push(val);
        this.upHeap(this.data.length - 1);
    }
    pop() {
        const min = this.data[0];
        const end = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = end;
            this.downHeap(0);
        }
        return min;
    }
}