堆積與優先佇列 — Min/Max Heap 原理與 Heap Sort 完整實作 | 資料結構與演算法

type Comparator<T> = (a: T, b: T) => number;

class MinHeap<T> {
  private heap: T[];
  private compare: Comparator<T>;

  constructor(comparator?: Comparator<T>) {
    this.heap = [];
    // 預設比較器：數字升序（Min-Heap）
    this.compare = comparator ?? ((a, b) => (a as unknown as number) - (b as unknown as number));
  }

  size(): number {
    return this.heap.length;
  }

  isEmpty(): boolean {
    return this.heap.length === 0;
  }

  // O(1)：直接讀取根節點
  peek(): T | undefined {
    return this.heap[0];
  }

  // O(log n)：插入後 Sift Up
  push(val: T): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }

  // O(log n)：取出根節點後 Sift Down
  pop(): T | undefined {
    if (this.isEmpty()) return undefined;
    this.swap(0, this.heap.length - 1);
    const min = this.heap.pop()!;
    this.siftDown(0);
    return min;
  }

  // O(n)：從陣列批次建堆（比逐一 push 更快）
  static heapify<T>(arr: T[], comparator?: Comparator<T>): MinHeap<T> {
    const h = new MinHeap<T>(comparator);
    h.heap = [...arr];
    // 從最後一個非葉節點往根節點方向執行 Sift Down
    for (let i = Math.floor(h.heap.length / 2) - 1; i >= 0; i--) {
      h.siftDown(i);
    }
    return h;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      // 若當前節點比父節點「更小」（依比較器），就上浮
      if (this.compare(this.heap[i], this.heap[parent]) < 0) {
        this.swap(i, parent);
        i = parent;
      } else {
        break; // 已滿足堆積性質，停止
      }
    }
  }

  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.compare(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      if (right < n && this.compare(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }

      if (smallest === i) break; // 當前節點已是最小，停止
      this.swap(i, smallest);
      i = smallest;
    }
  }

  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
}

// 使用範例：自訂比較器依物件欄位排序
interface Task {
  name: string;
  priority: number; // 數字越小，優先級越高
}

const taskQueue = new MinHeap<Task>((a, b) => a.priority - b.priority);
taskQueue.push({ name: "backup", priority: 3 });
taskQueue.push({ name: "deploy", priority: 1 });
taskQueue.push({ name: "test",   priority: 2 });

console.log(taskQueue.pop()?.name); // "deploy"（priority 最小 = 最高優先）
console.log(taskQueue.pop()?.name); // "test"
console.log(taskQueue.pop()?.name); // "backup"

// 用 MinHeap 模擬 MaxHeap：存入負數
const maxHeap = new MinHeap<number>();
maxHeap.push(-5);
maxHeap.push(-1);
maxHeap.push(-3);

// 取出時取負號還原為正數
const max = -maxHeap.pop()!; // 5（正確！）
console.log(max);            // 5

// 注意陷阱：忘記取負號會取到錯誤值
const wrong = maxHeap.pop(); // -3（這是負數，不是最大值 3）

// 更直覺的方式：比較器反轉
const maxHeap2 = new MinHeap<number>((a, b) => b - a); // b - a 即降序
maxHeap2.push(5);
maxHeap2.push(1);
maxHeap2.push(3);

console.log(maxHeap2.pop()); // 5（最大值先出）
console.log(maxHeap2.pop()); // 3
console.log(maxHeap2.pop()); // 1

// 原地排序：O(n log n) 時間，O(1) 額外空間
function heapSort(arr: number[]): number[] {
  const n = arr.length;

  // 階段一：原地建 Max-Heap（從最後一個非葉節點往根節點 Sift Down）
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDownMaxHeap(arr, n, i);
  }

  // 階段二：逐一取出最大值放到陣列末端
  for (let end = n - 1; end > 0; end--) {
    // 將根節點（目前最大值）與末端元素交換
    [arr[0], arr[end]] = [arr[end], arr[0]];
    // 對縮小後的堆（不含末端）重新 Sift Down
    siftDownMaxHeap(arr, end, 0);
  }

  return arr; // 結果為升序排列
}

function siftDownMaxHeap(arr: number[], n: number, i: number): void {
  while (true) {
    let largest = i;
    const left  = 2 * i + 1;
    const right = 2 * i + 2;

    if (left  < n && arr[left]  > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest === i) break;
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}

// 測試
console.log(heapSort([3, 1, 4, 1, 5, 9, 2, 6]));
// 輸出：[1, 1, 2, 3, 4, 5, 6, 9]

// 找陣列中最大的 K 個元素
// 策略：大小為 K 的 Min-Heap，root 是堆中最小值
// 若新元素 > root，就移除 root、加入新元素（保持堆中始終是目前最大的 K 個）
// 時間 O(n log k)，空間 O(k)——優於完整排序 O(n log n)
function topK(nums: number[], k: number): number[] {
  const heap = new MinHeap<number>();

  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) {
      heap.pop(); // 移除最小值，保持堆大小不超過 k
    }
  }

  // 收集結果（從小到大彈出，再反轉）
  const result: number[] = [];
  while (!heap.isEmpty()) {
    result.push(heap.pop()!);
  }
  return result.reverse(); // 由大到小
}

console.log(topK([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 3));
// 輸出：[9, 6, 5]

#include <queue>
#include <vector>
#include <iostream>
#include <functional>

void basicPriorityQueue() {
    // 預設：Max-Heap（最大值在頂部）
    std::priority_queue<int> maxPQ;
    maxPQ.push(3);
    maxPQ.push(1);
    maxPQ.push(4);
    std::cout << maxPQ.top() << "\n"; // 輸出：4

    // Min-Heap：必須明確指定 greater<int> 比較器
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;
    minPQ.push(3);
    minPQ.push(1);
    minPQ.push(4);
    std::cout << minPQ.top() << "\n"; // 輸出：1
}

struct Task {
    std::string name;
    int priority;
};

// priority_queue 的比較器：返回 true 表示「第一個參數優先度較低」
// 與 sort 的語義完全相反！
struct TaskComparator {
    bool operator()(const Task& a, const Task& b) const {
        // a.priority > b.priority：priority 小的先出（Min-Heap 效果）
        return a.priority > b.priority;
    }
};

void customComparatorExample() {
    std::priority_queue<Task, std::vector<Task>, TaskComparator> taskQueue;
    taskQueue.push({"backup", 3});
    taskQueue.push({"deploy", 1});
    taskQueue.push({"test",   2});

    while (!taskQueue.empty()) {
        // 輸出順序：deploy → test → backup
        std::cout << taskQueue.top().name << "\n";
        taskQueue.pop();
    }
}

void lambdaComparator() {
    // 依 pair 的 second 升序（Min-Heap）
    auto cmp = [](const std::pair<int,int>& a, const std::pair<int,int>& b) {
        return a.second > b.second;
    };
    std::priority_queue<
        std::pair<int,int>,
        std::vector<std::pair<int,int>>,
        decltype(cmp)
    > pq(cmp);

    pq.push({1, 5});
    pq.push({2, 3});
    pq.push({3, 7});
    std::cout << pq.top().first << "\n"; // 輸出：2（second = 3 最小）
}

#include <algorithm>

void stdHeapFunctions() {
    std::vector<int> v = {3, 1, 4, 1, 5};

    // 原地建 Max-Heap，O(n)
    std::make_heap(v.begin(), v.end());

    // 將新元素 push_back 後，呼叫 push_heap 維護堆積性質，O(log n)
    v.push_back(9);
    std::push_heap(v.begin(), v.end());

    // pop_heap 將最大值移到最後，O(log n)；再 pop_back 取出
    std::pop_heap(v.begin(), v.end());
    int maxVal = v.back();
    v.pop_back();
    std::cout << maxVal << "\n"; // 輸出：9
}

// 合併 K 個已排序陣列
// Heap 中每個元素存：[值, 陣列索引, 元素索引]
function mergeKSortedArrays(arrays: number[][]): number[] {
  const heap = new MinHeap<[number, number, number]>((a, b) => a[0] - b[0]);

  // 初始化：每個陣列的第一個元素入堆
  for (let i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) {
      heap.push([arrays[i][0], i, 0]);
    }
  }

  const result: number[] = [];

  while (!heap.isEmpty()) {
    const [val, arrayIdx, elemIdx] = heap.pop()!;
    result.push(val);

    // 將同一陣列的下一個元素加入 Heap
    const nextIdx = elemIdx + 1;
    if (nextIdx < arrays[arrayIdx].length) {
      heap.push([arrays[arrayIdx][nextIdx], arrayIdx, nextIdx]);
    }
  }

  return result;
}

// 測試
console.log(mergeKSortedArrays([
  [1, 4, 7],
  [2, 5, 8],
  [3, 6, 9],
]));
// 輸出：[1, 2, 3, 4, 5, 6, 7, 8, 9]
// 時間：O(N log K)，空間：O(K)（Heap 中最多 K 個元素）

// 雙堆法維護中位數
// maxHeap（左半部）：儲存較小的一半，root 是左半最大值
// minHeap（右半部）：儲存較大的一半，root 是右半最小值
// 不變量：
//   1. maxHeap.top ≤ minHeap.top（左半所有值 ≤ 右半所有值）
//   2. |maxHeap.size - minHeap.size| ≤ 1（兩半大小最多差 1）
class MedianFinder {
  // maxHeap 存負數以模擬 Max-Heap 行為
  private maxHeap: MinHeap<number>; // 儲存較小的一半
  private minHeap: MinHeap<number>; // 儲存較大的一半

  constructor() {
    this.maxHeap = new MinHeap<number>((a, b) => a - b); // 存負數
    this.minHeap = new MinHeap<number>();
  }

  addNum(num: number): void {
    // 步驟 1：新數先加入 maxHeap（存負數）
    this.maxHeap.push(-num);

    // 步驟 2：確保順序不變量：maxHeap.top ≤ minHeap.top
    if (!this.minHeap.isEmpty() && -this.maxHeap.peek()! > this.minHeap.peek()!) {
      this.minHeap.push(-this.maxHeap.pop()!);
    }

    // 步驟 3：確保大小不變量：maxHeap 最多比 minHeap 多 1 個
    if (this.maxHeap.size() > this.minHeap.size() + 1) {
      this.minHeap.push(-this.maxHeap.pop()!);
    } else if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.push(-this.minHeap.pop()!);
    }
  }

  findMedian(): number {
    // 總數為奇數：中位數在 maxHeap（多一個元素）
    if (this.maxHeap.size() > this.minHeap.size()) {
      return -this.maxHeap.peek()!;
    }
    // 總數為偶數：中位數是兩堆頂端的平均
    return (-this.maxHeap.peek()! + this.minHeap.peek()!) / 2;
  }
}

// 測試
const mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
console.log(mf.findMedian()); // 輸出：1.5
mf.addNum(3);
console.log(mf.findMedian()); // 輸出：2
mf.addNum(4);
console.log(mf.findMedian()); // 輸出：2.5
// addNum O(log n)，findMedian O(1)

// 錯誤：以為是 Min-Heap
std::priority_queue<int> pq;
pq.push(5); pq.push(1); pq.push(3);
int top = pq.top(); // 5（Max-Heap！不是 1）

// 正確：用 greater<int> 才是 Min-Heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;
minPQ.push(5); minPQ.push(1); minPQ.push(3);
int minTop = minPQ.top(); // 1（正確）

const maxHeap = new MinHeap<number>();
maxHeap.push(-5); maxHeap.push(-1); maxHeap.push(-3);

const wrong   = maxHeap.pop();  // -5（負數！不是最大值 5）
const correct = -maxHeap.pop()!; // 3（正確，取出後取負還原）

const nums = [3, 1, 4, 1, 5, 9, 2, 6];

// 慢：O(n log n)
const h1 = new MinHeap<number>();
for (const n of nums) h1.push(n); // 每次 push 是 O(log n)

// 快：O(n)
const h2 = MinHeap.heapify(nums); // 批次建堆

// n = 10^6 時，heapify 約 2×10^6 次操作；逐一 push 約 20×10^6 次

// 錯誤：先平衡大小再確保順序，可能讓 maxHeap.top > minHeap.top
addNumBug(num: number): void {
  this.maxHeap.push(-num);
  if (this.maxHeap.size() > this.minHeap.size() + 1) { // 先平衡大小
    this.minHeap.push(-this.maxHeap.pop()!);
  }
  // 此時可能 maxHeap.top > minHeap.top，中位數計算錯誤！
}

// 正確：必須先確保順序，再平衡大小（見上方 MedianFinder 實作）

function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap<number>();

  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) {
      heap.pop(); // 移除目前最小的，堆中始終保留最大的 k 個
    }
  }

  return heap.peek()!; // 堆頂就是第 k 大的元素
}

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

function topKFrequent(nums: number[], k: number): number[] {
  // 步驟 1：計算每個數字的出現頻率
  const freq = new Map<number, number>();
  for (const num of nums) {
    freq.set(num, (freq.get(num) ?? 0) + 1);
  }

  // 步驟 2：用 Min-Heap（依頻率）維護 Top-K
  // Heap 中存 [頻率, 數值]
  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);

  for (const [num, count] of freq) {
    heap.push([count, num]);
    if (heap.size() > k) {
      heap.pop(); // 移除頻率最低的
    }
  }

  // 步驟 3：收集結果
  const result: number[] = [];
  while (!heap.isEmpty()) {
    result.push(heap.pop()![1]);
  }
  return result;
}

console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // 輸出：[2, 1]（順序可能不同）

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val ?? 0;
    this.next = next ?? null;
  }
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  // Heap 中存 [節點值, 節點]，依值排序
  const heap = new MinHeap<[number, ListNode]>((a, b) => a[0] - b[0]);

  // 初始化：每個非空串列的頭節點入堆
  for (const node of lists) {
    if (node) heap.push([node.val, node]);
  }

  const dummy = new ListNode(0);
  let curr = dummy;

  while (!heap.isEmpty()) {
    const [, node] = heap.pop()!;
    curr.next = node;
    curr = curr.next;

    // 將該節點的下一個節點加入堆
    if (node.next) {
      heap.push([node.next.val, node.next]);
    }
  }

  return dummy.next;
}