15 — Heap & Priority Queue

What is a Heap?

Complete binary tree where parent ≥ children (max-heap) or parent ≤ children (min-heap).

Min-Heap:          Max-Heap:
     1                 9
    / \               / \
   3   5             7   6
  / \               / \
 7   9             3   5

Array: [1, 3, 5, 7, 9]    Array: [9, 7, 6, 3, 5]
Parent: i → Children: 2i+1, 2i+2
Child: i → Parent: (i-1)/2

---

Implementation

class MinHeap {
  private heap: number[] = [];
  
  push(val: number) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  pop(): number {
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return min;
  }
  
  peek(): number { return this.heap[0]; }
  size(): number { return this.heap.length; }
  
  private bubbleUp(i: number) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }
  
  private sinkDown(i: number) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

---

K-th Largest Element

function findKthLargest(nums: number[], k: number): number {
  const minHeap = new MinHeap();
  
  for (const num of nums) {
    minHeap.push(num);
    if (minHeap.size() > k) minHeap.pop(); // Keep only k largest
  }
  return minHeap.peek(); // k-th largest is the smallest in heap
}
// Time: O(n log k)

---

Merge K Sorted Lists

function mergeKLists(lists: ListNode[]): ListNode {
  // Min-heap of [value, listIndex]
  const heap = new MinHeap(); // Assume stores [val, node]
  
  // Add first element of each list
  for (const list of lists) {
    if (list) heap.push([list.val, list]);
  }
  
  const dummy = new ListNode(0);
  let current = dummy;
  
  while (heap.size() > 0) {
    const [val, node] = heap.pop();
    current.next = node;
    current = current.next;
    if (node.next) heap.push([node.next.val, node.next]);
  }
  
  return dummy.next;
}
// Time: O(N log k), N = total elements, k = number of lists

---

Median from Data Stream

class MedianFinder {
  private maxHeap: MaxHeap = new MaxHeap(); // Left half (larger values on top)
  private minHeap: MinHeap = new MinHeap(); // Right half (smaller values on top)
  
  addNum(num: number) {
    this.maxHeap.push(num);
    this.minHeap.push(this.maxHeap.pop()); // Move max of left to right
    
    // Balance: maxHeap can have at most 1 more element
    if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.push(this.minHeap.pop());
    }
  }
  
  findMedian(): number {
    if (this.maxHeap.size() > this.minHeap.size()) {
      return this.maxHeap.peek();
    }
    return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
  }
}

// addNum: O(log n), findMedian: O(1)

Stream: 5, 2, 8, 1, 9
maxHeap (left): [5]     minHeap (right): []        median: 5
maxHeap: [2]            minHeap: [5]               median: 3.5
maxHeap: [5, 2]         minHeap: [8]               median: 5
maxHeap: [2, 1]         minHeap: [5, 8]            median: 3.5
maxHeap: [5, 2, 1]      minHeap: [8, 9]            median: 5

---

Top K Frequent Elements

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  
  // Min-heap by frequency, keep k largest
  const heap = new MinHeap(); // Stores [freq, num]
  for (const [num, f] of freq) {
    heap.push([f, num]);
    if (heap.size() > k) heap.pop();
  }
  
  return heap.toArray().map(([_, num]) => num);
}

---

Key Takeaways

• Min-heap: smallest on top; Max-heap: largest on top
• Array representation: children at 2i+1, 2i+2; parent at (i-1)/2
• K-th largest: min-heap of size k → top is the answer
• Merge K sorted: min-heap of k heads → O(N log k)
• Median stream: max-heap (left) + min-heap (right) → O(1) median
• Heap = priority queue in interviews — know when to use min vs max