萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP SPL 數據結構:SplHeap 堆、SplMaxHeap 最大堆、SplMinHeap 最小堆完整指南

堆數據結構基礎

堆是完全二叉樹,滿足堆屬性:

  • 最大堆:父節點 ≥ 子節點,根節點為最大值
  • 最小堆:父節點 ≤ 子節點,根節點為最小值

常用於:優先隊列、堆排序、Top-K 問題、中位數維護。

SPL 堆類別體系

SplHeap (抽象類)
├── SplMaxHeap (最大堆,compare 返回 $b - $a)
└── SplMinHeap (最小堆,compare 返回 $a - $b)

核心方法

方法說明
insert($value)插入元素,自動上浮調整
top()返回堆頂元素(不移除)
extract()彈出並返回堆頂元素
count()元素數量
isEmpty()是否為空
recoverFromCorruption()修復損壞堆(罕用)
compare($a, $b)抽象方法,子類必須實現比較邏輯

自定義堆實現

<?php
// 最小堆:數值越小優先級越高
class MinHeap extends SplHeap {
    protected function compare($value1, $value2) {
        return $value1 - $value2; // 升序:小值在頂
    }
}

// 最大堆:數值越大優先級越高
class MaxHeap extends SplHeap {
    protected function compare($value1, $value2) {
        return $value2 - $value1; // 降序:大值在頂
    }
}

// 複雜對象堆:按優先級字段排序
class TaskPriorityHeap extends SplHeap {
    protected function compare($task1, $task2) {
        // 優先級高者在前(數值大 = 高優先級)
        return $task1['priority'] - $task2['priority'];
    }
}

// 使用
$heap = new TaskPriorityHeap();
$heap->insert(array('task' => 'email', 'priority' => 3));
$heap->insert(array('task' => 'backup', 'priority' => 1));
$heap->insert(array('task' => 'alert', 'priority' => 5));

while (!$heap->isEmpty()) {
    $task = $heap->extract();
    echo "Processing: {$task['task']} (priority {$task['priority']})\n";
}
// 輸出順序: alert(5) → email(3) → backup(1)

內建 SplMaxHeap / SplMinHeap 直接使用

<?php
// 最大堆
$maxHeap = new SplMaxHeap();
$maxHeap->insert(10);
$maxHeap->insert(5);
$maxHeap->insert(20);
$maxHeap->insert(15);

echo "Top: " . $maxHeap->top() . "\n"; // 20
echo "Count: " . $maxHeap->count() . "\n"; // 4

foreach ($maxHeap as $val) {
    echo "$val "; // 20 15 10 5 (迭代會消耗堆)
}
// 注意:foreach 會清空堆!需先 clone 或用 extract()

實戰應用:Top-K 問題

<?php
/**
 * 找出大數據流中前 K 大元素
 * 空間 O(K),時間 O(N log K)
 */
function topK($stream, $k) {
    $minHeap = new SplMinHeap(); // 維護大小為 K 的最小堆
    
    foreach ($stream as $value) {
        if ($minHeap->count() < $k) {
            $minHeap->insert($value);
        } elseif ($value > $minHeap->top()) {
            $minHeap->extract(); // 移除最小
            $minHeap->insert($value); // 插入更大
        }
    }
    
    // 提取結果(從小到大)
    $result = array();
    while (!$minHeap->isEmpty()) {
        $result[] = $minHeap->extract();
    }
    return array_reverse($result); // 返回降序
}

// 測試:100萬隨機數找前 10 大
$stream = function() {
    for ($i = 0; $i < 1000000; $i++) yield mt_rand(1, 10000000);
};

$top10 = topK($stream(), 10);
print_r($top10);

實戰應用:中位數維護

<?php
class MedianFinder {
    private $maxHeap; // 左半部:最大堆(存較小一半)
    private $minHeap; // 右半部:最小堆(存較大一半)
    
    public function __construct() {
        $this->maxHeap = new SplMaxHeap();
        $this->minHeap = new SplMinHeap();
    }
    
    public function addNum($num) {
        // 先加入最大堆
        $this->maxHeap->insert($num);
        // 平衡:將最大堆堆頂移至最小堆
        $this->minHeap->insert($this->maxHeap->extract());
        
        // 確保大小差 ≤ 1
        if ($this->maxHeap->count() < $this->minHeap->count()) {
            $this->maxHeap->insert($this->minHeap->extract());
        }
    }
    
    public function findMedian() {
        if ($this->maxHeap->count() > $this->minHeap->count()) {
            return $this->maxHeap->top();
        }
        return ($this->maxHeap->top() + $this->minHeap->top()) / 2;
    }
}

$mf = new MedianFinder();
foreach (array(1, 2, 3, 4, 5) as $n) {
    $mf->addNum($n);
    echo "Add $n, Median: " . $mf->findMedian() . "\n";
}

效能特徵

操作時間複雜度空間複雜度
insertO(log n)O(1)
topO(1)O(1)
extractO(log n)O(1)
buildHeap (批量)O(n)O(1)

注意事項

  1. foreach 會消耗堆:迭代過程中調用 extract(),循環結束堆為空
  2. 需保留堆請用 $copy = clone $heap; 或手動 extract() 存入陣列
  3. compare() 返回值:< 0 表示 $value1 優先級更高(在頂)
  4. 非數值比較需自行轉換(如字串用 strcmp)
  5. 大量插入考慮 SplFixedArray 預分配底層存儲

SPL Heap 提供標準庫級的堆實現,無需手寫二叉樹代碼,直接解決優先隊列、Top-K、中位數等經典算法問題。

copyright © 萬盛學電腦網 all rights reserved