Heap &
Priority Queue

10.1 Heap là gì?

Heap là binary tree thoả 2 tính chất:

1. Complete binary tree: tất cả các level đầy, level cuối điền từ trái sang phải
2. Heap property:
   • Min-heap: mỗi node ≤ các con
   • Max-heap: mỗi node ≥ các con

      Min-heap                    Max-heap
         [1]                         [9]
        /   \                       /   \
      [3]   [2]                   [7]   [8]
      / \   / \                   / \   / \
    [5] [4][8][6]               [3] [5][1][6]

10.2 Lưu Heap trong Array — không cần Node class

Vì heap là complete binary tree, ta có thể lưu trong array tuyến tính bằng công thức index:

Index:    0   1   2   3   4   5   6
Array:  [ 1, 3, 2, 5, 4, 8, 6 ]

Cây tương ứng:
              [0]
             /   \
           [1]   [2]
           / \   / \
         [3][4][5][6]

Quan hệ index:
- parent của i = (i - 1) / 2  (làm tròn xuống)
- left  con của i = 2*i + 1
- right con của i = 2*i + 2

function parent(i) { return Math.floor((i - 1) / 2); }
function left(i)   { return 2 * i + 1; }
function right(i)  { return 2 * i + 2; }

Cách lưu này cực kỳ hiệu quả — không cần pointer, cache-friendly, dễ duyệt.

10.3 Insert + Sift-up (Bubble-up) — O(log n)

Khi insert phần tử mới:

1. Thêm vào cuối array (giữ tính complete)
2. "Sift up": so với parent, swap nếu vi phạm heap property
3. Lặp đến khi đến root hoặc không cần swap

function siftUp(heap, i) {
  while (i > 0) {
    const p = Math.floor((i - 1) / 2);
    if (heap[i] < heap[p]) {  // min-heap: con < cha thì swap
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    } else break;
  }
}

function insert(heap, val) {
  heap.push(val);
  siftUp(heap, heap.length - 1);
}

Big-O: O(log n) vì sift-up đi tối đa height = log n.

10.4 Extract-min + Sift-down — O(log n)

Khi lấy phần tử min ra:

1. Lấy heap[0] (lưu lại để return)
2. Đưa phần tử cuối lên đầu (giữ complete)
3. "Sift down": so với 2 con, swap với con nhỏ hơn nếu vi phạm
4. Lặp đến khi không cần swap hoặc đến leaf

function siftDown(heap, i) {
  const n = heap.length;
  while (true) {
    const l = 2 * i + 1, r = 2 * i + 2;
    let smallest = i;
    if (l < n && heap[l] < heap[smallest]) smallest = l;
    if (r < n && heap[r] < heap[smallest]) smallest = r;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
}

function extractMin(heap) {
  if (heap.length === 0) return undefined;
  const min = heap[0];
  const last = heap.pop();
  if (heap.length > 0) {
    heap[0] = last;
    siftDown(heap, 0);
  }
  return min;
}

10.5 Heapify — Build heap từ array trong O(n) (KHÔNG phải O(n log n))

Tưởng chừng build heap = insert n lần × O(log n) = O(n log n). Nhưng có cách O(n):

function buildHeap(arr) {
  // Bắt đầu sift-down từ node parent của leaf cuối
  // Các leaf không cần sift-down (đã thoả heap property một mình)
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    siftDown(arr, i);
  }
  return arr;
}

Tại sao O(n)?

So sánh:

• Insert n lần: O(n log n)
• Heapify: O(n)

10.6 Cài đặt MinHeap đầy đủ

class MinHeap {
  constructor(compare = (a, b) => a - b) {
    this.data = [];
    this.compare = compare;  // < 0 nếu a < b
  }

  get size() { return this.data.length; }
  peek() { return this.data[0]; }

  push(val) {
    this.data.push(val);
    this._siftUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this._siftDown(0);
    }
    return top;
  }

  _siftUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.compare(this.data[i], this.data[p]) < 0) {
        [this.data[i], this.data[p]] = [this.data[p], this.data[i]];
        i = p;
      } else break;
    }
  }

  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let best = i;
      if (l < n && this.compare(this.data[l], this.data[best]) < 0) best = l;
      if (r < n && this.compare(this.data[r], this.data[best]) < 0) best = r;
      if (best === i) break;
      [this.data[i], this.data[best]] = [this.data[best], this.data[i]];
      i = best;
    }
  }

  // Build heap từ array trong O(n)
  static heapify(arr, compare) {
    const h = new MinHeap(compare);
    h.data = [...arr];
    for (let i = (h.data.length >> 1) - 1; i >= 0; i--) h._siftDown(i);
    return h;
  }
}

// Test
const h = new MinHeap();
[5, 3, 8, 1, 9, 2].forEach(x => h.push(x));
while (h.size) console.log(h.pop());  // 1, 2, 3, 5, 8, 9 (sorted!)

Max Heap chỉ là Min Heap với comparator đảo

const maxHeap = new MinHeap((a, b) => b - a);
[5, 3, 8].forEach(x => maxHeap.push(x));
maxHeap.pop();  // 8

Heap chứa object

// Min-heap theo priority
const tasks = new MinHeap((a, b) => a.priority - b.priority);
tasks.push({name: "A", priority: 3});
tasks.push({name: "B", priority: 1});
tasks.push({name: "C", priority: 2});
console.log(tasks.pop());  // {name: "B", priority: 1}

10.7 Pattern Top-K — vũ khí kinh điển

Bài toán: tìm k phần tử lớn nhất / nhỏ nhất trong mảng n phần tử.

Cách 1: Sort + slice — O(n log n)

function topK(arr, k) {
  return arr.slice().sort((a, b) => b - a).slice(0, k);
}

Cách 2: Min-heap kích thước k — O(n log k)

function topKHeap(arr, k) {
  const h = new MinHeap();  // min-heap để giữ k phần tử LỚN nhất
  for (const x of arr) {
    h.push(x);
    if (h.size > k) h.pop();  // bỏ phần tử nhỏ nhất
  }
  return [...h.data];
}

Tại sao dùng MIN-heap để tìm K LỚN nhất? Vì ta giữ k phần tử lớn nhất; phần tử nhỏ nhất trong nhóm đó cần dễ truy cập để loại bỏ khi gặp phần tử mới > nó. Ngược lại: tìm K nhỏ nhất → max-heap.

Cách 3: Quickselect — O(n) average

// Quickselect: tìm phần tử thứ k, sau đó partition lại
// Trung bình O(n), worst O(n²)
function findKthLargest(nums, k) {
  // Tương đương tìm phần tử thứ (n-k) smallest
  function quickselect(lo, hi, target) {
    if (lo === hi) return nums[lo];
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p];
    if (target < p) return quickselect(lo, p - 1, target);
    return quickselect(p + 1, hi, target);
  }
  return quickselect(0, nums.length - 1, nums.length - k);
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

So sánh 3 cách

Bài: Top K Frequent Elements

function topKFrequent(nums, k) {
  // Đếm tần suất
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);

  // Min-heap kích thước k theo frequency
  const h = new MinHeap((a, b) => a[1] - b[1]);  // [num, freq]
  for (const [num, f] of freq) {
    h.push([num, f]);
    if (h.size > k) h.pop();
  }
  return h.data.map(x => x[0]);
}

10.8 Two-Heap Technique — Median of Data Stream

Bài toán cực kinh điển: liên tục nhận số mới, sau mỗi lần thêm phải trả về median của tất cả số đã thấy. Đạt O(log n) per addNum.

Ý tưởng: chia số thành 2 nửa:

• Max-heap (lo): giữ nửa số nhỏ hơn — top là max của nửa nhỏ
• Min-heap (hi): giữ nửa số lớn hơn — top là min của nửa lớn
• Median = top(lo) nếu sizes lệch, hoặc avg(top(lo), top(hi)) nếu cân bằng

class MedianFinder {
  constructor() {
    this.lo = new MinHeap((a, b) => b - a);  // max-heap
    this.hi = new MinHeap();                   // min-heap
  }

  addNum(num) {
    // Đẩy vào lo trước
    this.lo.push(num);
    // Cân bằng: chuyển max của lo sang hi
    this.hi.push(this.lo.pop());
    // Đảm bảo lo có nhiều hơn hoặc bằng hi (cho median lẻ dễ hơn)
    if (this.hi.size > this.lo.size) {
      this.lo.push(this.hi.pop());
    }
  }

  findMedian() {
    if (this.lo.size > this.hi.size) return this.lo.peek();
    return (this.lo.peek() + this.hi.peek()) / 2;
  }
}

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

10.9 Ứng dụng khác của Heap

Merge K Sorted Lists/Arrays — O(N log k)

function mergeKSorted(lists) {
  const h = new MinHeap((a, b) => a.val - b.val);
  for (const head of lists) {
    if (head) h.push(head);
  }
  const dummy = {val: 0, next: null};
  let tail = dummy;
  while (h.size) {
    const node = h.pop();
    tail.next = node;
    tail = node;
    if (node.next) h.push(node.next);
  }
  return dummy.next;
}

Task Scheduler / Meeting Rooms II

// Có nhiều meeting với (start, end). Tìm số phòng tối thiểu cần thiết.
function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  // Min-heap chứa end time của các meeting đang dùng phòng
  const h = new MinHeap();
  for (const [start, end] of intervals) {
    if (h.size > 0 && h.peek() <= start) h.pop();  // tái dùng phòng
    h.push(end);
  }
  return h.size;
}

Dijkstra — sẽ học chương 11

Dijkstra dùng min-heap (priority queue) để chọn node có khoảng cách nhỏ nhất chưa thăm.

K Closest Points to Origin

function kClosest(points, k) {
  // Max-heap kích thước k theo distance (giữ k điểm gần nhất)
  const h = new MinHeap((a, b) => b[1] - a[1]);
  for (const p of points) {
    const d = p[0] * p[0] + p[1] * p[1];
    h.push([p, d]);
    if (h.size > k) h.pop();
  }
  return h.data.map(x => x[0]);
}

Bài tập

Tổng kết chương 10

• ✅ Heap = complete binary tree + heap property; lưu trong array với index (i-1)/2, 2i+1, 2i+2
• ✅ peek O(1), insert/extract O(log n), heapify O(n)
• ✅ Heap KHÔNG sort cả cây → search là O(n)
• ✅ Pattern Top-K: min-heap size k cho K lớn nhất; max-heap size k cho K nhỏ nhất
• ✅ Two-heap: bài median data stream — max-heap (nửa nhỏ) + min-heap (nửa lớn)
• ✅ JS không có Priority Queue built-in — phải tự cài MinHeap class với comparator tuỳ chỉnh
• ✅ Ứng dụng: Top K, Merge K Lists, Meeting Rooms, Dijkstra (chương 11)