Heaps & Priority Queues: Hướng Dẫn Toàn Diện

Array:   [1, 3, 2, 7, 6, 4, 5]
Index:    0  1  2  3  4  5  6
 
Ánh xạ sang cây:
         1 (i=0)
        / \
      3     2
    (i=1)  (i=2)
    / \    / \
   7   6  4   5
 (3) (4) (5) (6)

Insert 0 vào min heap [1, 3, 2, 7, 6, 4, 5]:
 
Bước 1: Thêm vào cuối → [1, 3, 2, 7, 6, 4, 5, 0]
Bước 2: Sift up 0
  - 0 < 7 (parent)? Có → swap → [1, 3, 2, 0, 6, 4, 5, 7]
  - 0 < 3 (parent)? Có → swap → [1, 0, 2, 3, 6, 4, 5, 7]
  - 0 < 1 (parent)? Có → swap → [0, 1, 2, 3, 6, 4, 5, 7]
  - Đã ở root → xong

Extract min từ [1, 3, 2, 7, 6, 4, 5]:
 
Bước 1: Lưu 1, đưa phần tử cuối lên root → [5, 3, 2, 7, 6, 4]
Bước 2: Sift down 5
  - Children: 3, 2. Child nhỏ hơn: 2 → 5 > 2? Có → swap → [2, 3, 5, 7, 6, 4]
  - Children: 4. Child nhỏ hơn: 4 → 5 > 4? Có → swap → [2, 3, 4, 7, 6, 5]
  - Không có children → xong
Kết quả: 1

// TypeScript - MinHeap Implementation
class MinHeap {
  private heap: number[] = [];
 
  get size(): number {
    return this.heap.length;
  }
 
  peek(): number | undefined {
    return this.heap[0];
  }
 
  insert(val: number): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  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()!;
    this.siftDown(0);
    return min;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i] >= this.heap[parent]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const 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[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
 
  // Build heap from array in O(n)
  static fromArray(arr: number[]): MinHeap {
    const heap = new MinHeap();
    heap.heap = [...arr];
    // Bắt đầu từ node non-leaf cuối cùng
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
      heap.siftDown(i);
    }
    return heap;
  }
}
 
// Sử dụng
const heap = new MinHeap();
heap.insert(5);
heap.insert(3);
heap.insert(8);
heap.insert(1);
 
console.log(heap.peek());       // 1
console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 3
console.log(heap.size);         // 2
 
// Build từ array
const heap2 = MinHeap.fromArray([7, 3, 9, 1, 5, 2]);
console.log(heap2.extractMin()); // 1
console.log(heap2.extractMin()); // 2
console.log(heap2.extractMin()); // 3

# Python - MinHeap Implementation
class MinHeap:
    def __init__(self):
        self.heap: list[int] = []
 
    @property
    def size(self) -> int:
        return len(self.heap)
 
    def peek(self) -> int | None:
        return self.heap[0] if self.heap else None
 
    def insert(self, val: int) -> None:
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
 
    def extract_min(self) -> int | None:
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
 
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return min_val
 
    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] >= self.heap[parent]:
                break
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
 
    def _sift_down(self, i: int) -> None:
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
 
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == i:
                break
 
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest
 
    @classmethod
    def from_array(cls, arr: list[int]) -> "MinHeap":
        heap = cls()
        heap.heap = arr[:]
        for i in range(len(arr) // 2 - 1, -1, -1):
            heap._sift_down(i)
        return heap
 
 
# Sử dụng
heap = MinHeap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
heap.insert(1)
 
print(heap.peek())        # 1
print(heap.extract_min())  # 1
print(heap.extract_min())  # 3
print(heap.size)           # 2
 
# Build từ array
heap2 = MinHeap.from_array([7, 3, 9, 1, 5, 2])
print(heap2.extract_min())  # 1
print(heap2.extract_min())  # 2
print(heap2.extract_min())  # 3

// TypeScript - MaxHeap Implementation
class MaxHeap {
  private heap: number[] = [];
 
  get size(): number {
    return this.heap.length;
  }
 
  peek(): number | undefined {
    return this.heap[0];
  }
 
  insert(val: number): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  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()!;
    this.siftDown(0);
    return max;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i] <= this.heap[parent]) break;  // So sánh đảo ngược
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
 
      if (left < n && this.heap[left] > this.heap[largest]) {
        largest = left;
      }
      if (right < n && this.heap[right] > this.heap[largest]) {
        largest = right;
      }
      if (largest === i) break;
 
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      i = largest;
    }
  }
}
 
// Sử dụng
const maxHeap = new MaxHeap();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
maxHeap.insert(1);
 
console.log(maxHeap.peek());       // 8
console.log(maxHeap.extractMax()); // 8
console.log(maxHeap.extractMax()); // 5

# Python - MaxHeap Implementation
class MaxHeap:
    def __init__(self):
        self.heap: list[int] = []
 
    @property
    def size(self) -> int:
        return len(self.heap)
 
    def peek(self) -> int | None:
        return self.heap[0] if self.heap else None
 
    def insert(self, val: int) -> None:
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
 
    def extract_max(self) -> int | None:
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
 
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return max_val
 
    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] <= self.heap[parent]:  # So sánh đảo ngược
                break
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
 
    def _sift_down(self, i: int) -> None:
        n = len(self.heap)
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
 
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            if largest == i:
                break
 
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            i = largest
 
 
# Sử dụng
max_heap = MaxHeap()
max_heap.insert(5)
max_heap.insert(3)
max_heap.insert(8)
max_heap.insert(1)
 
print(max_heap.peek())         # 8
print(max_heap.extract_max())  # 8
print(max_heap.extract_max())  # 5

# Python - Max heap dùng heapq (trick đảo dấu)
import heapq
 
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -8)
 
print(-heapq.heappop(max_heap))  # 8 (lớn nhất)
print(-heapq.heappop(max_heap))  # 5

// TypeScript - Priority Queue (Min Priority = highest priority)
interface PQItem<T> {
  value: T;
  priority: number;
}
 
class PriorityQueue<T> {
  private heap: PQItem<T>[] = [];
 
  get size(): number {
    return this.heap.length;
  }
 
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
 
  enqueue(value: T, priority: number): void {
    this.heap.push({ value, priority });
    this.siftUp(this.heap.length - 1);
  }
 
  dequeue(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop()!.value;
 
    const top = this.heap[0].value;
    this.heap[0] = this.heap.pop()!;
    this.siftDown(0);
    return top;
  }
 
  peek(): T | undefined {
    return this.heap[0]?.value;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i].priority >= this.heap[parent].priority) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
 
      if (left < n && this.heap[left].priority < this.heap[smallest].priority) {
        smallest = left;
      }
      if (right < n && this.heap[right].priority < this.heap[smallest].priority) {
        smallest = right;
      }
      if (smallest === i) break;
 
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}
 
// Sử dụng
const pq = new PriorityQueue<string>();
pq.enqueue("low priority task", 10);
pq.enqueue("critical bug", 1);
pq.enqueue("medium task", 5);
 
console.log(pq.dequeue()); // "critical bug" (priority 1)
console.log(pq.dequeue()); // "medium task" (priority 5)
console.log(pq.dequeue()); // "low priority task" (priority 10)

# Python - Priority Queue dùng heapq
import heapq
from dataclasses import dataclass, field
from typing import Any
 
@dataclass(order=True)
class PQItem:
    priority: int
    value: Any = field(compare=False)
 
class PriorityQueue:
    def __init__(self):
        self.heap: list[PQItem] = []
 
    @property
    def size(self) -> int:
        return len(self.heap)
 
    def is_empty(self) -> bool:
        return len(self.heap) == 0
 
    def enqueue(self, value: Any, priority: int) -> None:
        heapq.heappush(self.heap, PQItem(priority, value))
 
    def dequeue(self) -> Any | None:
        if not self.heap:
            return None
        return heapq.heappop(self.heap).value
 
    def peek(self) -> Any | None:
        return self.heap[0].value if self.heap else None
 
 
# Sử dụng
pq = PriorityQueue()
pq.enqueue("low priority task", 10)
pq.enqueue("critical bug", 1)
pq.enqueue("medium task", 5)
 
print(pq.dequeue())  # "critical bug" (priority 1)
print(pq.dequeue())  # "medium task" (priority 5)
print(pq.dequeue())  # "low priority task" (priority 10)

# Python - heapq module essentials
import heapq
 
# Tạo heap từ list (tại chỗ, O(n))
nums = [7, 3, 9, 1, 5, 2]
heapq.heapify(nums)
print(nums)  # [1, 3, 2, 7, 5, 9] — min heap hợp lệ
 
# Push và pop
heapq.heappush(nums, 0)
print(heapq.heappop(nums))  # 0
 
# Push và pop cùng lúc (hiệu quả hơn)
result = heapq.heapreplace(nums, 10)  # Pop nhỏ nhất, rồi push 10
print(result)  # 1
 
# Lấy K nhỏ nhất / lớn nhất
data = [7, 3, 9, 1, 5, 2, 8, 4, 6]
print(heapq.nsmallest(3, data))  # [1, 2, 3]
print(heapq.nlargest(3, data))   # [9, 8, 7]
 
# Heap với tuples (sắp xếp theo phần tử đầu)
tasks = []
heapq.heappush(tasks, (2, "medium task"))
heapq.heappush(tasks, (1, "urgent task"))
heapq.heappush(tasks, (3, "low task"))
 
print(heapq.heappop(tasks))  # (1, "urgent task")

// TypeScript - Heap Sort
function heapSort(arr: number[]): number[] {
  const n = arr.length;
 
  // Build max heap - bắt đầu từ node non-leaf cuối
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i);
  }
 
  // Extract từng phần tử
  for (let end = n - 1; end > 0; end--) {
    // Đưa root hiện tại (max) ra cuối
    [arr[0], arr[end]] = [arr[end], arr[0]];
    // Sift down trên heap đã thu nhỏ
    siftDown(arr, end, 0);
  }
 
  return arr;
}
 
function siftDown(arr: number[], heapSize: number, i: number): void {
  while (true) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
 
    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;
    if (largest === i) break;
 
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}
 
// Sử dụng
console.log(heapSort([7, 3, 9, 1, 5, 2, 8, 4, 6]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

# Python - Heap Sort
def heap_sort(arr: list[int]) -> list[int]:
    n = len(arr)
 
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)
 
    # Extract từng phần tử
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, end, 0)
 
    return arr
 
 
def sift_down(arr: list[int], heap_size: int, i: int) -> None:
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
 
        if left < heap_size and arr[left] > arr[largest]:
            largest = left
        if right < heap_size and arr[right] > arr[largest]:
            largest = right
        if largest == i:
            break
 
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest
 
 
# Sử dụng
print(heap_sort([7, 3, 9, 1, 5, 2, 8, 4, 6]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

// TypeScript - Kth Largest Element
function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap();
 
  for (const num of nums) {
    heap.insert(num);
    if (heap.size > k) {
      heap.extractMin();
    }
  }
 
  return heap.peek()!;
}
 
// Sử dụng
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

# Python - Kth Largest Element
import heapq
 
def find_kth_largest(nums: list[int], k: int) -> int:
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]
 
# One-liner
def find_kth_largest_v2(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]
 
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))  # 4

// TypeScript - Top K Frequent Elements
function topKFrequent(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 [frequency, number]
  const heap: [number, number][] = [];
 
  const siftUp = (i: number) => {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[i][0] >= heap[parent][0]) break;
      [heap[i], heap[parent]] = [heap[parent], heap[i]];
      i = parent;
    }
  };
 
  const siftDown = (i: number) => {
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] < heap[smallest][0]) smallest = l;
      if (r < heap.length && heap[r][0] < heap[smallest][0]) smallest = r;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  };
 
  for (const [num, count] of freq) {
    heap.push([count, num]);
    siftUp(heap.length - 1);
    if (heap.length > k) {
      heap[0] = heap.pop()!;
      siftDown(0);
    }
  }
 
  return heap.map(([_, num]) => num);
}
 
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [2, 1] hoặc [1, 2]

# Python - Top K Frequent Elements
import heapq
from collections import Counter
 
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    # nlargest trả về k items có counts cao nhất
    return heapq.nlargest(k, freq.keys(), key=freq.get)
 
# Cách khác: min heap size k
def top_k_frequent_v2(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for count, num in heap]
 
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))  # [1, 2]

// TypeScript - Merge K Sorted Lists
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
 
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  // Min heap lưu [value, listIndex]
  const heap: [number, number][] = [];
 
  const siftUp = (i: number) => {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i][0] >= heap[p][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
 
  const siftDown = (i: number) => {
    while (true) {
      let s = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
      if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  };
 
  const push = (item: [number, number]) => {
    heap.push(item);
    siftUp(heap.length - 1);
  };
 
  const pop = (): [number, number] => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    siftDown(0);
    return top;
  };
 
  // Khởi tạo heap với head của mỗi list
  const heads = [...lists];
  for (let i = 0; i < heads.length; i++) {
    if (heads[i]) push([heads[i]!.val, i]);
  }
 
  const dummy = new ListNode();
  let current = dummy;
 
  while (heap.length > 0) {
    const [val, idx] = pop();
    current.next = new ListNode(val);
    current = current.next;
 
    heads[idx] = heads[idx]!.next;
    if (heads[idx]) push([heads[idx]!.val, idx]);
  }
 
  return dummy.next;
}

# Python - Merge K Sorted Lists
import heapq
from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    # Dùng index làm tiebreaker (ListNode không comparable)
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
 
    dummy = ListNode()
    current = dummy
 
    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = ListNode(val)
        current = current.next
 
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))
 
    return dummy.next

// TypeScript - Median Finder với Two Heaps
class MedianFinder {
  private lo: MaxHeap; // max heap — nửa dưới
  private hi: MinHeap; // min heap — nửa trên
 
  constructor() {
    this.lo = new MaxHeap();
    this.hi = new MinHeap();
  }
 
  addNum(num: number): void {
    // Luôn thêm vào max heap trước
    this.lo.insert(num);
 
    // Đảm bảo max nửa dưới ≤ min nửa trên
    if (this.hi.size > 0 && this.lo.peek()! > this.hi.peek()!) {
      this.hi.insert(this.lo.extractMax()!);
    }
 
    // Cân bằng size: lo có thể lớn hơn tối đa 1
    if (this.lo.size > this.hi.size + 1) {
      this.hi.insert(this.lo.extractMax()!);
    } else if (this.hi.size > this.lo.size) {
      this.lo.insert(this.hi.extractMin()!);
    }
  }
 
  findMedian(): number {
    if (this.lo.size > this.hi.size) {
      return this.lo.peek()!;
    }
    return (this.lo.peek()! + this.hi.peek()!) / 2;
  }
}
 
// Sử dụng
const mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
console.log(mf.findMedian()); // 1.5
mf.addNum(3);
console.log(mf.findMedian()); // 2

# Python - Median Finder với Two Heaps
import heapq
 
class MedianFinder:
    def __init__(self):
        self.lo: list[int] = []  # max heap (đảo dấu)
        self.hi: list[int] = []  # min heap
 
    def add_num(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
 
        # Đảm bảo max nửa dưới ≤ min nửa trên
        if self.hi and -self.lo[0] > self.hi[0]:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
 
        # Cân bằng size
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
 
    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2
 
 
# Sử dụng
mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median())  # 1.5
mf.add_num(3)
print(mf.find_median())  # 2.0

// TypeScript - K Closest Points to Origin
function kClosest(points: number[][], k: number): number[][] {
  // Max heap theo khoảng cách (đảo dấu để có max behavior dùng min heap logic)
  const heap: [number, number[]][] = []; // [negDist, point]
 
  const siftUp = (i: number) => {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i][0] <= heap[p][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
 
  const siftDown = (i: number) => {
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] > heap[largest][0]) largest = l;
      if (r < heap.length && heap[r][0] > heap[largest][0]) largest = r;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  };
 
  for (const point of points) {
    const dist = point[0] ** 2 + point[1] ** 2;
    heap.push([dist, point]);
    siftUp(heap.length - 1);
    if (heap.length > k) {
      heap[0] = heap.pop()!;
      siftDown(0);
    }
  }
 
  return heap.map(([_, point]) => point);
}
 
console.log(kClosest([[1, 3], [-2, 2]], 1)); // [[-2, 2]]

# Python - K Closest Points to Origin
import heapq
 
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # Max heap size k (đảo dấu distance)
    heap = []
    for x, y in points:
        dist = -(x * x + y * y)  # đảo dấu cho max heap
        heapq.heappush(heap, (dist, [x, y]))
        if len(heap) > k:
            heapq.heappop(heap)
    return [point for _, point in heap]
 
print(k_closest([[1, 3], [-2, 2]], 1))  # [[-2, 2]]

// TypeScript - Task Scheduler
function leastInterval(tasks: string[], n: number): number {
  const freq = new Map<string, number>();
  for (const task of tasks) {
    freq.set(task, (freq.get(task) || 0) + 1);
  }
 
  // Max heap of frequencies
  const heap: number[] = [];
  const pushHeap = (val: number) => {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i] <= heap[p]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const popHeap = (): number => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    let i = 0;
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l] > heap[largest]) largest = l;
      if (r < heap.length && heap[r] > heap[largest]) largest = r;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
    return top;
  };
 
  for (const count of freq.values()) {
    pushHeap(count);
  }
 
  const cooldown: [number, number][] = []; // [count, availableTime]
  let time = 0;
 
  while (heap.length > 0 || cooldown.length > 0) {
    time++;
 
    if (heap.length > 0) {
      const count = popHeap() - 1;
      if (count > 0) {
        cooldown.push([count, time + n]);
      }
    }
 
    if (cooldown.length > 0 && cooldown[0][1] === time) {
      pushHeap(cooldown.shift()![0]);
    }
  }
 
  return time;
}
 
console.log(leastInterval(["A","A","A","B","B","B"], 2)); // 8

# Python - Task Scheduler
import heapq
from collections import Counter, deque
 
def least_interval(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
    # Max heap (đảo dấu cho max behavior)
    heap = [-count for count in freq.values()]
    heapq.heapify(heap)
 
    cooldown = deque()  # (count, available_time)
    time = 0
 
    while heap or cooldown:
        time += 1
 
        if heap:
            count = heapq.heappop(heap) + 1  # +1 vì đã đảo dấu
            if count < 0:
                cooldown.append((count, time + n))
 
        if cooldown and cooldown[0][1] == time:
            heapq.heappush(heap, cooldown.popleft()[0])
 
    return time
 
print(least_interval(["A","A","A","B","B","B"], 2))  # 8

// TypeScript - Reorganize String
function reorganizeString(s: string): string {
  const freq = new Map<string, number>();
  for (const c of s) {
    freq.set(c, (freq.get(c) || 0) + 1);
  }
 
  // Max heap of [count, char]
  const heap: [number, string][] = [];
  const push = (item: [number, string]) => {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i][0] <= heap[p][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const pop = (): [number, string] => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    let i = 0;
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] > heap[largest][0]) largest = l;
      if (r < heap.length && heap[r][0] > heap[largest][0]) largest = r;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
    return top;
  };
 
  for (const [char, count] of freq) {
    push([count, char]);
  }
 
  let result = "";
  let prev: [number, string] | null = null;
 
  while (heap.length > 0) {
    const [count, char] = pop();
    result += char;
 
    if (prev && prev[0] > 0) {
      push(prev);
    }
 
    prev = [count - 1, char];
  }
 
  return result.length === s.length ? result : "";
}
 
console.log(reorganizeString("aab"));   // "aba"
console.log(reorganizeString("aaab"));  // ""

# Python - Reorganize String
import heapq
from collections import Counter
 
def reorganize_string(s: str) -> str:
    freq = Counter(s)
    # Max heap (đảo dấu counts)
    heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(heap)
 
    result = []
    prev = None  # (neg_count, char)
 
    while heap:
        neg_count, char = heapq.heappop(heap)
        result.append(char)
 
        if prev and prev[0] < 0:
            heapq.heappush(heap, prev)
 
        prev = (neg_count + 1, char)  # +1 vì đã đảo dấu
 
    return "".join(result) if len(result) == len(s) else ""
 
print(reorganize_string("aab"))   # "aba"
print(reorganize_string("aaab"))  # ""

// TypeScript - Meeting Rooms II
function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
 
  // Min heap of end times
  const heap: number[] = [];
  const push = (val: number) => {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i] >= heap[p]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const pop = (): number => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    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 top;
  };
 
  for (const [start, end] of intervals) {
    // Nếu phòng kết thúc sớm nhất đã rảnh, tái sử dụng
    if (heap.length > 0 && heap[0] <= start) {
      pop();
    }
    push(end);
  }
 
  return heap.length;
}
 
console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2
console.log(minMeetingRooms([[7,10],[2,4]]));           // 1

# Python - Meeting Rooms II
import heapq
 
def min_meeting_rooms(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    heap = []  # min heap of end times
 
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
 
    return len(heap)
 
print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))            # 1