Ranking & Ordering

[!NOTE] This module explores the core principles of Heaps Practice Problems, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

A Heap (Priority Queue) allows O(1) access to the min/max element and O(log N) insertion/deletion. It is the go-to structure for “Top K” problems or dynamic ordering.

Core Patterns:

1. Kth Largest/Smallest: Use a Min-Heap of size K to keep the K largest elements.
2. Top K Frequent: Map counts, then Heap.
3. Merge K Sorted: Min-Heap to track the smallest current head across all lists.

---

2. Interactive Analysis: Kth Largest Stream

Find the 3rd largest element in a stream. We keep a Min-Heap of size 3. If a new number is larger than the Heap’s minimum (root), we replace it. The root is always the 3rd largest.

Heap (Size 3): []

3rd Largest: -

---

3. Top K Frequent Elements

Problem: Given [1,1,1,2,2,3] and k=2, return [1, 2].

Intuition

1. Count Frequencies: Hash Map O(N).
2. Keep Top K: Min-Heap of size K O(N log K).
   • Heap stores (count, value).
   • If heap size > K, pop min (lowest frequency). The survivors are the K most frequent.

Solutions

Java

Go

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);

    // Min-Heap based on frequency
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> count.get(a) - count.get(b));

    for (int n : count.keySet()) {
        heap.add(n);
        if (heap.size() > k) heap.poll(); // Remove least frequent
    }

    int[] res = new int[k];
    for (int i = 0; i < k; i++) res[i] = heap.poll();
    return res;
}

func topKFrequent(nums []int, k int) []int {
    count := make(map[int]int)
    for _, n := range nums { count[n]++ }

    h := &MinHeap{}
    heap.Init(h)

    for num, freq := range count {
        heap.Push(h, Element{num, freq})
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    res := make([]int, k)
    for i := 0; i < k; i++ {
        res[i] = heap.Pop(h).(Element).val
    }
    return res
}

// Boilerplate Go Heap omitted for brevity

---

4. Complexity Analysis

Strategy	Time	Space	Notes
Sorting	O(N log N)	O(N)	Simple, but slower for large N.
Min-Heap	O(N log K)	O(K)	Optimal for K « N (Streaming compatible).
QuickSelect	O(N) Avg	O(1)	Modifies array, not stable.