Heap / Priority Queue — The Complete Guide

For element at index i:
  Parent:      Math.floor((i - 1) / 2)
  Left child:  2 * i + 1
  Right child: 2 * i + 2

Example min-heap:
        1
       / \
      3    5
     / \  /
    7   8 9

Array: [1, 3, 5, 7, 8, 9]

Key operations:
  peek()    → O(1)      — return root (min or max)
  insert()  → O(log n)  — add at end, bubble UP
  extract() → O(log n)  — remove root, move last to root, bubble DOWN
  heapify() → O(n)      — build heap from unsorted array (not O(n log n)!)

function topK(items: Item[], k: number): Item[] {
  const minHeap = new MinPriorityQueue<Item>({
    compare: (a, b) => score(a) - score(b),
  });

  for (const item of items) {
    minHeap.enqueue(item);
    if (minHeap.size() > k) {
      minHeap.dequeue(); // remove the weakest
    }
  }

  // Heap now contains the K best items
  return minHeap.toArray();
}
// Time: O(n log k)  Space: O(k)
// Key: min-heap for top-K largest, max-heap for top-K smallest
// The root is always the "weakest" member of the top-K club

function mergeKSorted(lists: number[][]): number[] {
  const minHeap = new MinPriorityQueue<{val: number, listIdx: number, elemIdx: number}>({
    compare: (a, b) => a.val - b.val,
  });

  // Seed heap with first element from each list
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) {
      minHeap.enqueue({ val: lists[i][0], listIdx: i, elemIdx: 0 });
    }
  }

  const result: number[] = [];
  while (minHeap.size() > 0) {
    const { val, listIdx, elemIdx } = minHeap.dequeue();
    result.push(val);

    // Push next element from the same list
    if (elemIdx + 1 < lists[listIdx].length) {
      minHeap.enqueue({
        val: lists[listIdx][elemIdx + 1],
        listIdx,
        elemIdx: elemIdx + 1,
      });
    }
  }

  return result;
}
// Time: O(N log K) where N = total elements, K = number of lists
// Space: O(K) — heap holds at most K elements at any time
// Key: heap always has at most one element per source list

class MedianFinder {
  private lo = new MaxPriorityQueue<number>(); // max-heap: lower half
  private hi = new MinPriorityQueue<number>(); // min-heap: upper half

  addNum(num: number): void {
    // Step 1: Add to appropriate heap
    if (this.lo.size() === 0 || num <= this.lo.front()) {
      this.lo.enqueue(num);
    } else {
      this.hi.enqueue(num);
    }

    // Step 2: Rebalance — sizes differ by at most 1
    if (this.lo.size() > this.hi.size() + 1) {
      this.hi.enqueue(this.lo.dequeue());
    } else if (this.hi.size() > this.lo.size()) {
      this.lo.enqueue(this.hi.dequeue());
    }
  }

  findMedian(): number {
    if (this.lo.size() > this.hi.size()) {
      return this.lo.front();
    }
    return (this.lo.front() + this.hi.front()) / 2;
  }
}
// Time: O(log n) per addNum, O(1) per findMedian
// Space: O(n)
// Key: lo.size() === hi.size() or lo.size() === hi.size() + 1
// Median is always at lo.front() or average of both fronts

function minCostProcess(tasks: Task[]): number {
  const minHeap = new MinPriorityQueue<Task>({
    compare: (a, b) => a.cost - b.cost,
  });

  // Load all tasks
  for (const task of tasks) {
    minHeap.enqueue(task);
  }

  let totalCost = 0;
  while (minHeap.size() > 1) {
    // Greedily pick the cheapest options
    const first = minHeap.dequeue();
    const second = minHeap.dequeue();

    const combined = combine(first, second);
    totalCost += combined.cost;

    // Push the result back for future processing
    minHeap.enqueue(combined);
  }

  return totalCost;
}
// When to use: connect ropes/sticks, Huffman coding,
// minimum cost to merge stones, task scheduler
// Key: greedy choice + re-insertion into heap

function topKFrequent(nums: number[], k: number): number[] {
  // Step 1: Count frequencies — O(n)
  const freq = new Map<number, number>();
  for (const num of nums) {
    freq.set(num, (freq.get(num) ?? 0) + 1);
  }

  // Step 2: Min-heap of size k, ordered by frequency
  const minHeap = new MinPriorityQueue<[number, number]>({
    compare: (a, b) => a[1] - b[1], // compare by frequency
  });

  for (const [num, count] of freq) {
    minHeap.enqueue([num, count]);
    if (minHeap.size() > k) {
      minHeap.dequeue(); // remove least frequent
    }
  }

  // Step 3: Extract results
  return minHeap.toArray().map(([num]) => num);
}
// Time: O(n log k) — n for counting, m log k for heap (m = unique elements)
// Space: O(n) for frequency map + O(k) for heap
// Alternative: Bucket sort gives O(n) but uses O(n) space

function leastInterval(tasks: string[], n: number): number {
  // Count frequencies
  const freq = new Map<string, number>();
  for (const task of tasks) {
    freq.set(task, (freq.get(task) ?? 0) + 1);
  }

  // Max-heap by frequency
  const maxHeap = new MaxPriorityQueue<number>();
  for (const count of freq.values()) {
    maxHeap.enqueue(count);
  }

  let time = 0;
  while (maxHeap.size() > 0) {
    const cooldown: number[] = [];
    // Process up to n+1 tasks in this cycle
    for (let i = 0; i <= n; i++) {
      if (maxHeap.size() > 0) {
        const count = maxHeap.dequeue();
        if (count - 1 > 0) {
          cooldown.push(count - 1);
        }
      }
      time++;
      // If both heap and cooldown are empty, we're done
      if (maxHeap.size() === 0 && cooldown.length === 0) break;
    }
    // Re-add tasks that still have remaining count
    for (const count of cooldown) {
      maxHeap.enqueue(count);
    }
  }

  return time;
}
// Time: O(n × totalTasks) in worst case, but typically much faster
// Key insight: greedily pick the most frequent task each cycle
// to minimize idle slots

nums = [3, 2, 1, 5, 6, 4], k = 2
Min-heap of size 2 — root = kth largest

Process 3: heap = [3]           size=1 (< k, just add)
Process 2: heap = [2, 3]        size=2 (= k, heap is full)
Process 1: 1 < root(2)?         YES → skip (too small for top-2)
           heap = [2, 3]
Process 5: 5 > root(2)?         YES → add, remove root
           heap = [3, 5]        root=3 (new kth largest)
Process 6: 6 > root(3)?         YES → add, remove root
           heap = [5, 6]        root=5 (new kth largest)
Process 4: 4 < root(5)?         YES → skip (too small for top-2)
           heap = [5, 6]

Answer: root = 5 (2nd largest)

Key observations:
- Heap never exceeds size k=2
- Root is always the SMALLEST of the top-k → the kth largest
- Elements smaller than root are immediately rejected
- Each insertion/removal is O(log k) = O(log 2) = O(1) here

lo = max-heap (lower half)    hi = min-heap (upper half)
Rule: lo.size >= hi.size, and lo.size <= hi.size + 1

Add 5:
  lo = [5]    hi = []
  Balance: lo.size(1) = hi.size(0) + 1 ✓
  Median = lo.top = 5

Add 15:
  15 > lo.top(5) → add to hi
  lo = [5]    hi = [15]
  Balance: lo.size(1) = hi.size(1) ✓
  Median = (5 + 15) / 2 = 10

Add 1:
  1 <= lo.top(5) → add to lo
  lo = [5, 1]    hi = [15]
  Balance: lo.size(2) = hi.size(1) + 1 ✓
  Median = lo.top = 5

Add 3:
  3 <= lo.top(5) → add to lo
  lo = [5, 3, 1]    hi = [15]
  Balance: lo.size(3) > hi.size(1) + 1 → REBALANCE
  Move lo.top(5) to hi
  lo = [3, 1]    hi = [5, 15]
  Balance: lo.size(2) = hi.size(2) ✓
  Median = (3 + 5) / 2 = 4

Visual at the end:
  Lower half (max-heap):  [3, 1]     ← top is 3
  Upper half (min-heap):  [5, 15]    ← top is 5
  
  All sorted: 1, 3 | 5, 15
                  ↑   ↑
              lo.top  hi.top → median = (3+5)/2 = 4

Key observations:
- lo always holds the smaller half, hi the larger half
- lo.top ≤ hi.top (the halves don't overlap)
- Median is always accessible in O(1) from the tops
- Rebalancing is O(log n) but happens at most once per insertion

Do you REPEATEDLY need the min or max from a CHANGING collection?
├── NO  → Not a heap problem. Consider sorting, single pass, or QuickSelect.
└── YES → What specifically do you need?
          ├── Top-K or Kth element?
          │   ├── K largest → Min-heap of size K
          │   └── K smallest → Max-heap of size K
          ├── Merge K sorted sources?
          │   └── Min-heap of K elements (one per source)
          ├── Running median or balance between halves?
          │   └── Two heaps: max-heap (lower) + min-heap (upper)
          └── Greedy: always pick the best option?
              └── Heap ordered by priority/cost/frequency

Which heap type?
├── Need the SMALLEST at the top → Min-heap
├── Need the LARGEST at the top  → Max-heap
└── Need BOTH extremes           → Two heaps

Heap size?
├── Fixed at K (top-K problems)  → Cap with: if (size > k) dequeue()
├── Fixed at K (merge-K)         → One element per source, never exceeds K
├── Unbounded (greedy/scheduling) → Grows and shrinks as items are processed
└── Two heaps (median)           → Combined size = n, each ≈ n/2