10-Heap

Buổi 10 — Heap (Priority Queue)

Navigation

← 09-Graph-DFS-BFS | → 11-Practice-Big-Tech-1 Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

---

1. Analogy & Context

Heap = Phòng cấp cứu bệnh viện (Emergency Room Triage)

Hãy tưởng tượng phòng cấp cứu của một bệnh viện lớn:

• Bệnh nhân không được xử lý theo thứ tự đến — người đến trước không nhất thiết được khám trước
• Bệnh nhân được xử lý theo mức độ nghuy hiểm (priority): tim ngừng đập > gãy tay > ho nhẹ
• Y tá triage liên tục đánh giá lại — bệnh nhân mới nghiêm trọng hơn sẽ “chen lên” trên

Min-Heap = Bệnh nhân ưu tiên số nhỏ nhất Priority number 1 = critical → được xử lý trước. extractMin() lấy ra bệnh nhân urgent nhất.

Max-Heap = Bệnh nhân ưu tiên số lớn nhất Đảo ngược: số lớn hơn = quan trọng hơn. Dùng cho “top K largest” problems.

Min-Heap vs Max-Heap — Quick Rule

• Min-Heap: extractMin() → luôn lấy phần tử nhỏ nhất ra trước
• Max-Heap: extractMax() → luôn lấy phần tử lớn nhất ra trước
• JavaScript/TypeScript không có built-in heap → phải tự implement hoặc simulate

Context thực tế:

• Task Scheduler: OS scheduling processes by priority
• Dijkstra’s Algorithm: luôn process node có distance nhỏ nhất tiếp theo
• Merge K sorted files: merge log files từ K servers
• Real-time leaderboard: top K players
• Event-driven simulation: process events theo timestamp
• Huffman coding: build optimal prefix codes (data compression)

---

2. The FAANG Standard

"Top K" Problems = Heap Territory

Nếu bạn thấy từ khóa “top K”, “K-th largest/smallest”, “merge K”, “median” — đó là dấu hiệu cần dùng Heap. Heap cho $O(\log K)$ per operation thay vì $O(N\log N)$ nếu sort toàn bộ.

Những gì FAANG interviewer mong đợi:

Kỹ năng	Mức độ quan trọng	Ghi chú
Biết heap là gì, cách hoạt động	⭐⭐⭐⭐⭐	Không được nhầm với BST
Implement MinHeap từ đầu	⭐⭐⭐⭐	Google hay hỏi
Top-K pattern với min-heap	⭐⭐⭐⭐⭐	Counter-intuitive: dùng MIN heap cho top K LARGEST
Merge K sorted lists	⭐⭐⭐⭐⭐	L5 classic
Median of data stream	⭐⭐⭐⭐⭐	Two heaps approach — L5 standard
Task Scheduler	⭐⭐⭐	Greedy + heap
Dijkstra’s (weighted shortest path)	⭐⭐⭐	L5/L6, heap + dist array

L4 expectation: Giải được Top-K, kth largest, biết dùng heap khi nào.

L5 expectation: Implement heap, giải Merge K Sorted Lists, Median from Stream, explain trade-offs vs sort.

---

3. Visual Thinking (Mermaid)

3.1 Binary Heap — Array Representation và Index Formula

graph TD
    A["arr[0] = 1<br/>(root)"]
    B["arr[1] = 3"]
    C["arr[2] = 5"]
    D["arr[3] = 7"]
    E["arr[4] = 9"]
    F["arr[5] = 8"]
    G["arr[6] = 10"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

    style A fill:#e74c3c,color:#fff

Index formulas:
  parent(i)     = Math.floor((i - 1) / 2)
  leftChild(i)  = 2 * i + 1
  rightChild(i) = 2 * i + 2

Array: [1, 3, 5, 7, 9, 8, 10]
         0  1  2  3  4  5   6

3.2 Heapify Up (Insert) Process

flowchart TD
    subgraph Step1["Step 1: Insert 2 tại cuối"]
        S1["[1, 3, 5, 7, 9, 8, 10, 2]<br/>             ↑ new"]
    end

    subgraph Step2["Step 2: Bubble up — compare 2 với parent 7"]
        S2["2 < 7 → swap!<br/>[1, 3, 5, 2, 9, 8, 10, 7]"]
    end

    subgraph Step3["Step 3: Compare 2 với parent 3"]
        S3["2 < 3 → swap!<br/>[1, 2, 5, 3, 9, 8, 10, 7]"]
    end

    subgraph Step4["Step 4: Compare 2 với parent 1"]
        S4["2 > 1 → STOP<br/>Heap property restored"]
    end

    Step1 --> Step2 --> Step3 --> Step4

3.3 Heapify Down (Extract-Min) Process

flowchart TD
    subgraph Step1["Step 1: Remove root (1), move last element to root"]
        S1["[10, 3, 5, 7, 9, 8]<br/>  ↑ last element (10) becomes root"]
    end

    subgraph Step2["Step 2: Sift down — 10 vs children 3, 5 → smaller child = 3"]
        S2["10 > 3 → swap!<br/>[3, 10, 5, 7, 9, 8]"]
    end

    subgraph Step3["Step 3: 10 vs children 7, 9 → smaller child = 7"]
        S3["10 > 7 → swap!<br/>[3, 7, 5, 10, 9, 8]"]
    end

    subgraph Step4["Step 4: 10 có no children → STOP"]
        S4["Heap property restored<br/>Min = 3 (extracted)"]
    end

    Step1 --> Step2 --> Step3 --> Step4

3.4 Two Heaps for Median

graph LR
    subgraph MaxHeap["Max-Heap (lower half)<br/>[1, 2, 3, 4, 5]"]
        direction TB
        M5((5)) --> M3((3))
        M5 --> M4((4))
        M3 --> M1((1))
        M3 --> M2((2))
    end

    MEDIAN["Median = (5 + 6) / 2 = 5.5"]

    subgraph MinHeap["Min-Heap (upper half)<br/>[6, 8, 9]"]
        direction TB
        N6((6)) --> N8((8))
        N6 --> N9((9))
    end

    MaxHeap --> MEDIAN
    MEDIAN --> MinHeap

    style MEDIAN fill:#f39c12,color:#000

---

4. TypeScript Template

4.1 MinHeap Class — Complete Implementation

class MinHeap {
  private heap: number[];
 
  constructor() {
    this.heap = [];
  }
 
  // Helper: index formulas
  private parent(i: number): number { return Math.floor((i - 1) / 2); }
  private left(i: number): number { return 2 * i + 1; }
  private right(i: number): number { return 2 * i + 2; }
 
  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
 
  // Insert: O(log N)
  insert(val: number): void {
    this.heap.push(val);
    this.heapifyUp(this.heap.length - 1);
  }
 
  private heapifyUp(i: number): void {
    while (i > 0 && this.heap[i] < this.heap[this.parent(i)]) {
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }
 
  // Extract minimum: O(log N)
  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
 
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!; // Move last to root
    this.heapifyDown(0);
    return min;
  }
 
  private heapifyDown(i: number): void {
    const n = this.heap.length;
    let smallest = i;
 
    const l = this.left(i);
    const r = this.right(i);
 
    if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
    if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
 
    if (smallest !== i) {
      this.swap(i, smallest);
      this.heapifyDown(smallest);
    }
  }
 
  // Peek minimum without removing: O(1)
  peek(): number | undefined {
    return this.heap[0];
  }
 
  size(): number {
    return this.heap.length;
  }
}
 
// MaxHeap: chỉ thay đổi comparison direction
class MaxHeap {
  private heap: number[];
 
  constructor() { this.heap = []; }
 
  private parent(i: number): number { return Math.floor((i - 1) / 2); }
  private left(i: number): number { return 2 * i + 1; }
  private right(i: number): number { return 2 * i + 2; }
  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
 
  insert(val: number): void {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0 && this.heap[i] > this.heap[this.parent(i)]) { // Changed: > instead of <
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }
 
  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
 
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    let i = 0;
    const n = this.heap.length;
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.heap[l] > this.heap[largest]) largest = l;
      if (r < n && this.heap[r] > this.heap[largest]) largest = r;
      if (largest === i) break;
      this.swap(i, largest);
      i = largest;
    }
    return max;
  }
 
  peek(): number | undefined { return this.heap[0]; }
  size(): number { return this.heap.length; }
}

Off-by-one Index — Nhớ công thức này

parent(i)     = Math.floor((i - 1) / 2)   ← không phải i/2
leftChild(i)  = 2 * i + 1
rightChild(i) = 2 * i + 2

Root ở index 0. Nếu root ở index 1 (một số sách dạy vậy), công thức sẽ khác: parent = i/2, left = 2i, right = 2i+1.

4.2 kthLargestElement — Min-Heap of Size K

// LeetCode #215: Kth Largest Element in an Array
// Approach: Dùng min-heap size K
// Heap luôn chứa K phần tử lớn nhất đã thấy
// Root của min-heap = phần tử nhỏ nhất trong K phần tử lớn nhất = Kth largest
 
function findKthLargest(nums: number[], k: number): number {
  const minHeap = new MinHeap();
 
  for (const num of nums) {
    minHeap.insert(num);
 
    if (minHeap.size() > k) {
      minHeap.extractMin(); // Loại bỏ phần tử nhỏ nhất — không thuộc top K
    }
  }
 
  return minHeap.peek()!; // Root = Kth largest
}
 
// ===== TEST CASES =====
// [3,2,1,5,6,4], k=2 → 5
// Sau khi process: heap = [5, 6], root = 5 = 2nd largest ✓
 
// [3,2,3,1,2,4,5,5,6], k=4 → 4
// Top 4 largest: [6, 5, 5, 4], Kth largest = 4 ✓
 
// ===== COMPLEXITY =====
// Time: O(N log K) — N elements, each insert/extract is O(log K)
// Space: O(K) — heap contains at most K+1 elements at any time
// vs Sort approach: O(N log N) time, O(1) space
// Khi K << N: O(N log K) << O(N log N)

Counter-intuitive: Dùng MIN-heap cho top K LARGEST

Logic: Min-heap chứa K phần tử lớn nhất. Root = smallest trong K lớn nhất = Kth largest overall. Khi thêm phần tử mới: nếu nó lớn hơn root → nó thuộc top K, extract root (loại K+1-th), insert mới. Nếu dùng max-heap: phải giữ N-K+1 phần tử nhỏ nhất — tốn hơn.

4.3 mergeKSortedLists

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
 
// Approach: Min-heap luôn chứa head của mỗi list còn lại
// Mỗi lần extract min, advance pointer trong list đó
 
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  // Simulate min-heap với sorted array (trong interview thực tế)
  // Trong production: dùng proper heap implementation
  type HeapEntry = { val: number; node: ListNode };
 
  // Proper binary min-heap on HeapEntry — KHÔNG dùng sort+shift!
  // sort+shift mỗi insert là O(N log N) → tổng O(NK log K · log K) — sai complexity.
  const heap: HeapEntry[] = [];
 
  const heapPush = (entry: HeapEntry): void => {
    heap.push(entry);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p].val <= heap[i].val) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
 
  const heapPop = (): HeapEntry | undefined => {
    if (heap.length === 0) return undefined;
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n = heap.length;
      while (true) {
        const l = 2*i + 1, r = 2*i + 2;
        let smallest = i;
        if (l < n && heap[l].val < heap[smallest].val) smallest = l;
        if (r < n && heap[r].val < heap[smallest].val) smallest = r;
        if (smallest === i) break;
        [heap[smallest], heap[i]] = [heap[i], heap[smallest]];
        i = smallest;
      }
    }
    return top;
  };
 
  // Initialize: add head of each non-null list
  for (const head of lists) {
    if (head) heapPush({ val: head.val, node: head });
  }
 
  const dummy = new ListNode(0);
  let curr = dummy;
 
  while (heap.length > 0) {
    const { node } = heapPop()!;
    curr.next = node;
    curr = curr.next;
 
    if (node.next) {
      heapPush({ val: node.next.val, node: node.next });
    }
  }
 
  return dummy.next;
}
 
// ===== COMPLEXITY =====
// K = số lists, N = tổng số nodes
// Time: O(N log K) — N nodes, mỗi lần insert/extract là O(log K)
// Space: O(K) — heap chứa tối đa K elements (một head per list)
// vs Naive merge: O(N * K) — merge từng pair
// vs Sort all: O(N log N)

4.4 findMedianFromDataStream — Two Heaps

Xem phần 8 cho complete solution đầy đủ.

// Concept sketch — chi tiết ở Section 8
class MedianFinder {
  // lower half — max-heap (lưu nửa nhỏ hơn)
  private lowerMaxHeap: MaxHeap;
  // upper half — min-heap (lưu nửa lớn hơn)
  private upperMinHeap: MinHeap;
 
  constructor() {
    this.lowerMaxHeap = new MaxHeap();
    this.upperMinHeap = new MinHeap();
  }
 
  addNum(num: number): void {
    // Thêm vào lower half trước
    this.lowerMaxHeap.insert(num);
 
    // Balance: max của lower phải <= min của upper
    if (
      this.upperMinHeap.size() > 0 &&
      this.lowerMaxHeap.peek()! > this.upperMinHeap.peek()!
    ) {
      this.upperMinHeap.insert(this.lowerMaxHeap.extractMax()!);
    }
 
    // Balance sizes: lower có thể nhiều hơn upper 1 phần tử (nếu total là số lẻ)
    if (this.lowerMaxHeap.size() > this.upperMinHeap.size() + 1) {
      this.upperMinHeap.insert(this.lowerMaxHeap.extractMax()!);
    } else if (this.upperMinHeap.size() > this.lowerMaxHeap.size()) {
      this.lowerMaxHeap.insert(this.upperMinHeap.extractMin()!);
    }
  }
 
  findMedian(): number {
    if (this.lowerMaxHeap.size() === this.upperMinHeap.size()) {
      return (this.lowerMaxHeap.peek()! + this.upperMinHeap.peek()!) / 2;
    }
    return this.lowerMaxHeap.peek()!; // Lower luôn lớn hơn hoặc bằng upper
  }
}

4.5 topKFrequentElements

// LeetCode #347: Top K Frequent Elements
// Approach 1: Sort by frequency O(N log N)
// Approach 2: Min-heap of size K O(N log K) — better khi K << N
// Approach 3: Bucket sort O(N) — optimal!
 
function topKFrequent(nums: number[], k: number): number[] {
  // Count frequencies
  const freq = new Map<number, number>();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
 
  // Bucket sort: buckets[i] = list of numbers with frequency i
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }
 
  // Collect top K from highest frequency buckets
  const result: number[] = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
 
  return result.slice(0, k);
}
 
// ===== COMPLEXITY =====
// Time: O(N) — bucket sort approach
// Space: O(N) — freq map + buckets
 
// Heap approach (Min-Heap size K) — O(N log K)
// CHÚ Ý: dùng REAL binary heap, không phải sort+shift (sort+shift là O(N² log N)!)
function topKFrequentHeap(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const num of nums) freq.set(num, (freq.get(num) || 0) + 1);
 
  // Min-heap of [freq, num] — root là freq nhỏ nhất.
  // Khi heap size > k, pop root (freq nhỏ nhất) → giữ K phần tử freq lớn nhất.
  const heap: [number, number][] = [];
 
  const push = (item: [number, number]) => {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n = heap.length;
      while (true) {
        const l = 2*i + 1, r = 2*i + 2;
        let s = i;
        if (l < n && heap[l][0] < heap[s][0]) s = l;
        if (r < n && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[s], heap[i]] = [heap[i], heap[s]];
        i = s;
      }
    }
    return top;
  };
 
  for (const [num, count] of freq) {
    push([count, num]);
    if (heap.length > k) pop(); // Bỏ phần tử có freq nhỏ nhất → O(log K)
  }
 
  return heap.map(([, num]) => num);
}

---

5. Complexity Deep-dive

Heap Operations

Operation	Time	Space	Ghi chú
Insert	$O(\log N)$	$O(1)$	Heapify up — tối đa H levels
Extract-Min/Max	$O(\log N)$	$O(1)$	Heapify down — tối đa H levels
Peek	$O(1)$	$O(1)$	Root luôn ở index 0
Build Heap từ array	$O(N)$	$O(1)$	Không phải $O(N\log N)$!
Search	$O(N)$	$O(1)$	Heap không hỗ trợ fast search
Delete arbitrary	$O(\log N)$	$O(1)$	Sau khi tìm được node: O(N) find + O(log N) fix

Tại sao Build Heap là $O(N)$, không phải $O(N\log N)$?

Trực giác: Khi build heap bằng cách heapify từ dưới lên (không phải insert từng phần tử):

• Nodes ở level thấp nhất (nhiều nhất) chỉ cần sift down 0 bước
• Nodes ở level tiếp theo cần tối đa 1 bước
• Chỉ root (1 node) cần sift down $\log N$ bước

$T={\sum }_{h=0}^{\log N}\frac{N}{2^{h+1}}\cdot h=O(N)$

O(N) Build Heap — Khi nào dùng?

Build heap O(N) chỉ hữu ích khi bạn có sẵn toàn bộ array ngay từ đầu. Nếu elements đến theo stream (online), phải insert từng cái → O(log N) per element → O(N log N) total.

Top-K Comparison

Approach	Time	Space	Khi nào dùng
Sort toàn bộ	$O(N\log N)$	$O(1)$	K gần bằng N
Min-Heap size K	$O(N\log K)$	$O(K)$	K << N (thường dùng)
QuickSelect	$O(N)$ average	$O(1)$	Chỉ cần Kth element, không cần sort
Bucket Sort	$O(N)$	$O(N)$	Khi values bounded (như frequency)

$O(N\log K)\ll O(N\log N)\text{ khi }K\ll N$

---

6. Edge Cases & Pitfalls

JavaScript/TypeScript không có built-in Heap

// WRONG: Dùng array.sort() mỗi lần insert → O(N) per insert
const heap: number[] = [];
heap.push(val);
heap.sort((a, b) => a - b); // O(N log N)! Không phải heap!
 
// CORRECT: Implement MinHeap class với heapifyUp/Down
// Hoặc dùng thư viện ngoài (trong competitive programming)
// Trong FAANG interview: implement từ đầu hoặc giả định có heap

Off-by-One trong Index Formula

// Nhớ: root ở index 0 (zero-indexed)
parent(i)     = Math.floor((i - 1) / 2)  // Không phải Math.floor(i / 2)
leftChild(i)  = 2 * i + 1                // Không phải 2 * i
rightChild(i) = 2 * i + 2                // Không phải 2 * i + 1
 
// Nếu root ở index 1 (one-indexed — một số code dùng):
parent(i)     = Math.floor(i / 2)
leftChild(i)  = 2 * i
rightChild(i) = 2 * i + 1

Top-K Largest: Dùng MIN-Heap, không phải MAX-Heap

Counter-intuitive nhất trong heap problems:

• Muốn top K largest → dùng min-heap size K
• Lý do: cần extract (loại bỏ) những phần tử nhỏ hơn Kth largest
• Min-heap root = smallest trong top K = “threshold” — nếu new element > root, nó thuộc top K
• Max-heap size K: sẽ loại phần tử lớn nhất → sai!

Two Heaps for Median — Balancing Rule

Invariant cần maintain:

1. lowerMaxHeap.peek() <= upperMinHeap.peek() — tất cả phần tử của lower ≤ tất cả phần tử của upper
2. |lowerSize - upperSize| <= 1 — hai heap gần bằng nhau về size (lower có thể nhiều hơn 1 nếu total lẻ)

Sau mỗi addNum, check và restore cả hai invariants theo thứ tự.

Heap vs Sorted Array — Trade-offs

	Heap	Sorted Array
Insert	O(log N)	O(N) — shift elements
Extract min/max	O(log N)	O(1) — take from end
Search	O(N)	O(log N) — binary search
Dùng khi	Dynamic stream, frequent insert/extract	Static data, frequent search

---

7. Pattern Recognition

Khi thấy những từ khóa này → nghĩ đến Heap:

Từ khóa trong đề	Pattern
”top K elements”	Min-heap size K, $O(N\log K)$
“K-th largest / smallest”	Min/Max-heap size K, hoặc QuickSelect
”merge K sorted lists/arrays”	Min-heap with K heads
”median of data stream”	Two heaps (max lower + min upper)
“sliding window maximum”	Monotonic deque hoặc max-heap
”task scheduler / CPU scheduling”	Max-heap by frequency
”connect ropes with min cost”	Min-heap, greedy
”find closest K points”	Max-heap size K (by distance)
“stream / online algorithm”	Heap — maintain invariant incrementally

Heap vs Deque vs Segment Tree

• Top K from static array: Sort $O(N\log N)$ hoặc QuickSelect $O(N)$
• Top K from stream: Min/Max-heap $O(N\log K)$
• Sliding window max/min: Monotonic Deque $O(N)$ — heap sẽ là $O(N\log N)$
• Range max/min queries: Segment Tree $O(\log N)$ per query

Heap là workhorse cho “dynamic top K” — nhưng có những bài cần cấu trúc khác.

---

8. Top LeetCode Problems

Danh sách theo thứ tự học

#	Problem	Difficulty	Kỹ năng cần	Ghi chú
LC-215 #215	Kth Largest Element in Array	Medium	Min-heap size K	Warm-up cho heap
LC-347 #347	Top K Frequent Elements	Medium	Heap + freq map	Nhiều approaches
LC-703 #703	Kth Largest in Stream	Easy	Min-heap maintain	Online algorithm
LC-23 #23	Merge K Sorted Lists	Hard	Min-heap với K heads	L5 classic
LC-295 #295	Find Median from Data Stream	Hard	Two heaps	Must-know L5
LC-621 #621	Task Scheduler	Medium	Max-heap by freq	Greedy + heap
LC-378 #378	Kth Smallest in Sorted Matrix	Medium	Min-heap	Matrix + heap
LC-355 #355	Design Twitter	Medium	Heap + design	System design mini
LC-1046 #1046	Last Stone Weight	Easy	Max-heap	Simple greedy

---

Complete Solution: #295 Find Median from Data Stream

Problem Statement

Implement MedianFinder class:

• addNum(num): thêm một số từ data stream
• findMedian(): trả về median của tất cả số đã thêm

Median = trung bình cộng hai số giữa (nếu số lượng chẵn) hoặc số giữa (nếu số lượng lẻ).

Tại sao Two Heaps?

• Naive: sort lại sau mỗi addNum → $O(N\log N)$ per call
• Binary search insert: $O(\log N)$ tìm vị trí, $O(N)$ shift → $O(N)$ total per call
• Two heaps: $O(\log N)$ per addNum, $O(1)$ per findMedian

Key Insight: Median nằm ở ranh giới giữa nửa nhỏ hơn và nửa lớn hơn. Ta dùng:

• lowerMaxHeap: chứa nửa nhỏ hơn — max-heap để $O(1)$ access phần tử lớn nhất của nửa này
• upperMinHeap: chứa nửa lớn hơn — min-heap để $O(1)$ access phần tử nhỏ nhất của nửa này

class MedianFinder {
  // lowerMaxHeap chứa nửa nhỏ hơn — root = max của lower half
  private lower: number[]; // Max-heap (negate values for min-heap simulation)
  // upperMinHeap chứa nửa lớn hơn — root = min của upper half
  private upper: number[]; // Min-heap
 
  constructor() {
    this.lower = []; // Simulated max-heap bằng cách negate
    this.upper = []; // Min-heap thực sự
  }
 
  // Min-heap operations (standard)
  private heapPushMin(heap: number[], val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[i] < heap[parent]) {
        [heap[i], heap[parent]] = [heap[parent], heap[i]];
        i = parent;
      } else break;
    }
  }
 
  private heapPopMin(heap: number[]): number {
    if (heap.length === 1) return heap.pop()!;
    const min = heap[0];
    heap[0] = heap.pop()!;
    let i = 0;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l] < heap[smallest]) smallest = l;
      if (r < heap.length && heap[r] < heap[smallest]) smallest = r;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
    return min;
  }
 
  // Max-heap = negate values, use min-heap operations
  private heapPushMax(heap: number[], val: number): void {
    this.heapPushMin(heap, -val); // Negate để turn max-heap thành min-heap
  }
 
  private heapPopMax(heap: number[]): number {
    return -this.heapPopMin(heap); // Negate lại khi lấy ra
  }
 
  private peekMax(heap: number[]): number {
    return -heap[0]; // Negate để get actual value
  }
 
  private peekMin(heap: number[]): number {
    return heap[0];
  }
 
  addNum(num: number): void {
    // Bước 1: Luôn thêm vào lower half trước
    this.heapPushMax(this.lower, num);
 
    // Bước 2: Đảm bảo max(lower) <= min(upper)
    // Nếu vi phạm, move max của lower sang upper
    if (
      this.upper.length > 0 &&
      this.peekMax(this.lower) > this.peekMin(this.upper)
    ) {
      const maxOfLower = this.heapPopMax(this.lower);
      this.heapPushMin(this.upper, maxOfLower);
    }
 
    // Bước 3: Balance sizes
    // Invariant: lower.size == upper.size (chẵn) hoặc lower.size == upper.size + 1 (lẻ)
    if (this.lower.length > this.upper.length + 1) {
      // Lower có quá nhiều → move max của lower sang upper
      const maxOfLower = this.heapPopMax(this.lower);
      this.heapPushMin(this.upper, maxOfLower);
    } else if (this.upper.length > this.lower.length) {
      // Upper có nhiều hơn → move min của upper sang lower
      const minOfUpper = this.heapPopMin(this.upper);
      this.heapPushMax(this.lower, minOfUpper);
    }
  }
 
  findMedian(): number {
    if (this.lower.length === this.upper.length) {
      // Tổng số chẵn → median = average của hai số giữa
      return (this.peekMax(this.lower) + this.peekMin(this.upper)) / 2;
    }
    // Tổng số lẻ → lower có nhiều hơn 1 phần tử → root của lower là median
    return this.peekMax(this.lower);
  }
}
 
// ===== TEST CASES =====
const mf = new MedianFinder();
 
mf.addNum(1);
// lower: [1], upper: []
// findMedian() → 1.0
 
mf.addNum(2);
// lower: [1], upper: [2]  (balanced, even total)
// findMedian() → (1 + 2) / 2 = 1.5
 
mf.addNum(3);
// lower: [1], upper: [2, 3]? → after balance: lower: [2], upper: [3]? No...
// addNum(3): push to lower → lower: [2, 1], upper: [2]... let's trace:
// Step 1: push 3 to lower → lower (max-heap): [2, 1, 3] → after heapify: [3, 1, 2]
// Step 2: peekMax(lower) = 3, peekMin(upper) = 2 → 3 > 2 → move 3 to upper
//         lower: [2, 1], upper: [2, 3]
// Step 3: lower.size = 2, upper.size = 2 → balanced? No, upper > lower!
//         move minOfUpper (2) to lower
//         lower: [2, 1, 2] → [2, 1, 2] max-heap, upper: [3]
// findMedian() → lower.size (3) > upper.size (1) + 1? No, 3 == 1 + 1? No 3 > 2...
// Hmm, re-trace more carefully with fresh MedianFinder...
 
// Simpler test:
// addNum(1): lower:[1], upper:[] → median: 1.0
// addNum(2): lower:[1], upper:[] → push 2 to lower → lower:[2,1]
//            peekMax(lower)=2, upper empty → skip step 2
//            lower.size=2 > upper.size=0+1=1 → move max(2) to upper
//            lower:[1], upper:[2]
//            findMedian: equal sizes → (1+2)/2 = 1.5 ✓
// addNum(3): push 3 to lower → lower:[3,1]
//            peekMax(lower)=3, peekMin(upper)=2 → 3>2 → move 3 to upper
//            lower:[1], upper:[2,3]
//            upper.size=2 > lower.size=1 → move min(2) to lower
//            lower:[2,1], upper:[3]
//            findMedian: lower.size=2 > upper.size=1, lower has 1 more → median = peekMax(lower) = 2 ✓
 
// ===== COMPLEXITY =====
// addNum:    O(log N) — heap insert + possible rebalance (constant number of O(log N) ops)
// findMedian: O(1) — just peek at two heap roots
// Space: O(N) — store all N numbers across two heaps
 
// ===== FOLLOW-UP =====
// Q: Nếu 90% numbers từ [0, 100], làm sao optimize?
// A: Bucket sort + two pointers. Chỉ cần đếm distribution vào 101 buckets,
//    dùng prefix sum để tìm median index.

Two Heaps Invariants — Phải maintain cả hai

1. Order invariant: max(lower) <= min(upper) — tất cả phần tử lower ≤ tất cả phần tử upper
2. Size invariant: lower.size == upper.size hoặc lower.size == upper.size + 1

Thứ tự fix: Order trước, Size sau. Nếu fix Size trước mà không fix Order, có thể tạo ra vi phạm Order mới.

---

9. Self-Assessment Checklist

Kiểm tra kiến thức của bạn

Heap Fundamentals:

• Giải thích được min-heap property và array representation
• Tính được parent/child indices không cần nhìn gợi ý
• Giải thích tại sao heapify-up và heapify-down là $O(\log N)$
• Giải thích tại sao build-heap là $O(N)$, không phải $O(N\log N)$

Implementation:

• Implement MinHeap với insert và extractMin trong 15 phút
• Implement MaxHeap bằng cách negate values (tái sử dụng MinHeap logic)
• Không bị off-by-one trong index formulas

Problem Patterns:

• Giải thích tại sao Top-K Largest dùng MIN-heap (counter-intuitive)
• Viết được findKthLargest với min-heap size K
• Giải thích được Merge K Sorted Lists approach và complexity
• Giải thích được two-heap approach cho Median of Stream

Two Heaps (Median):

• Giải thích được hai invariants cần maintain
• Viết được addNum với proper rebalancing
• Giải thích tại sao fix Order invariant trước Size invariant

Trade-offs:

• So sánh được $O(N\log K)$ vs $O(N\log N)$ cho Top-K
• Biết khi nào dùng Heap vs QuickSelect vs Sort
• Biết khi nào dùng Heap vs Monotonic Deque (sliding window)

---

Tags: dsa heap priority-queue top-k median faang algorithm Liên quan: 09-Graph-DFS-BFS | 11-Practice-Big-Tech-1 | MOC-DSA-Mastery