PHP 堆積排序演算法實作：最小堆建構、逐步調整、原地排序完整解析

堆積排序是時間複雜度 O(n log n) 的原地排序演算法。本文以 PHP 實作最小堆，詳細解析節點索引關係、adjustNode 下沉調整、heapSort 主流程、swap 位元運算交換，並附帶執行前後結構圖解，適合演算法學習與面試準備。

堆積基本概念

• 完全二元樹： 除最後一層外皆滿，最後一層靠左排列
• 最小堆： 父節點 ≤ 子節點，堆頂為最小值
• 陣列索引對應 (1-based)：
  • 父節點：i >> 1 (或 intdiv($i, 2))
  • 左子節點：i << 1 (或 $i * 2)
  • 右子節點：(i << 1) + 1 (或 $i * 2 + 1)

範例資料結構演變

原始陣列: [1, 8, 7, 2, 3, 4, 6, 5, 9]
樹狀結構:
         1
       /   \
      8     7
     / \   / \
    2   3 4   6
   /
  5 9

排序後 (最小堆):
         1
       /   \
      2     3
     / \   / \
    4   5 6   7
   /
  8 9

最終陣列: [1, 2, 3, 4, 5, 6, 7, 8, 9]

完整 PHP 實作

<?php
/**
 * 堆積排序 (最小堆，遞增排序)
 * @param array &$arr 參考傳遞，原地排序
 */
function heapSort(&$arr) {
    $n = count($arr);
    if ($n <= 1) return;

    // 1-based 索引：陣列前插入佔位元素
    array_unshift($arr, null);  // $arr[0] 不使用
    $last = $n;  // 最後一個元素索引

    // 從最後一個非葉節點開始向上調整
    for ($i = $last >> 1; $i >= 1; $i--) {
        adjustNode($i, $last, $arr);
    }

    // 重複：堆頂與末尾交換、縮小堆範圍、調整新堆頂
    while ($last > 1) {
        // 將最小值 (堆頂) 移至已排序區末尾
        swap($arr[1], $arr[$last]);
        $last--;

        // 調整新堆頂，維持堆性質
        adjustNode(1, $last, $arr);
    }

    // 移除佔位元素，還原 0-based 陣列
    array_shift($arr);
}

/**
 * 向下調整節點，維持最小堆性質
 * @param int   $i     當前節點索引
 * @param int   $last  堆有效範圍末尾
 * @param array &$arr  陣列參考
 */
function adjustNode($i, $last, &$arr) {
    $left = $i << 1;  // 左子節點
    if ($left > $last) return;  // 無子節點

    $right = $left + 1;  // 右子節點
    $smallest = $left;

    // 找出左右子節點中較小者
    if ($right <= $last && $arr[$right] < $arr[$left]) {
        $smallest = $right;
    }

    // 若子節點小於父節點，交換並遞迴向下調整
    if ($arr[$smallest] < $arr[$i]) {
        swap($arr[$smallest], $arr[$i]);
        adjustNode($smallest, $last, $arr);
    }
}

/**
 * 位元運算交換 (無需暫存變數)
 * @param mixed &$a
 * @param mixed &$b
 */
function swap(&$a, &$b) {
    $a ^= $b;
    $b ^= $a;
    $a ^= $b;
}

// === 測試 ===
$arr = [1, 8, 7, 2, 3, 4, 6, 5, 9];
echo "排序前: " . implode(', ', $arr) . "\n";
heapSort($arr);
echo "排序後: " . implode(', ', $arr) . "\n";
// 輸出: 1, 2, 3, 4, 5, 6, 7, 8, 9
?>

關鍵步驟逐行追蹤

複雜度分析

• 時間複雜度： O(n log n) — 建堆 O(n) + n 次調整 O(log n)
• 空間複雜度： O(1) — 原地排序，僅使用常數額外空間
• 穩定性： 不穩定 — 相等元素相對順序可能改變

與 PHP 內建排序比較

<?php
$data = [1, 8, 7, 2, 3, 4, 6, 5, 9];

// 內建排序 (快速排序變體，平均 O(n log n))
sort($data);  // 直接修改陣列
// 或
$sorted = $data;
sort($sorted);

// 內建支援使用者自訂比較
usort($data, function($a, $b) { return $a - $b; });

實務建議： 生產環境**永遠使用內建 sort()/usort()**，經過高度優化、C 實作、支援 Timsort (PHP 7+)、穩定且效能遠超使用者空間實作。本文實作僅供演算法學習與教學用途。

常見變體與應用

• Top-K 問題： 建大小為 K 的最小堆，掃描陣列維持堆大小，最終堆內即為前 K 大元素
• 中位數維護： 雙堆 (大頂堆+小頂堆) 動態維護串流中位數
• 優先佇列： 堆是實作優先佇列的標準資料結構
• 外部排序： 檔案過大無法載入記憶體時，分塊排序後用 K-way merge (最小堆) 合併

遞迴改寫為迭代 (避免棧溢位)

function adjustNodeIterative($i, $last, &$arr) {
    while (true) {
        $left = $i << 1;
        if ($left > $last) break;
        $right = $left + 1;
        $smallest = $left;
        if ($right <= $last && $arr[$right] < $arr[$left]) $smallest = $right;
        if ($arr[$smallest] < $arr[$i]) {
            swap($arr[$smallest], $arr[$i]);
            $i = $smallest;
        } else {
            break;
        }
    }
}

掌握堆積排序的核心邏輯與變體應用，是演算法工程師的基本功，亦是解決海量資料 Top-K、串流中位數等經典問題的利器。