堆是完全二叉樹,滿足堆屬性:
常用於:優先隊列、堆排序、Top-K 問題、中位數維護。
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)
<?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()
<?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";
}
| 操作 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| insert | O(log n) | O(1) |
| top | O(1) | O(1) |
| extract | O(log n) | O(1) |
| buildHeap (批量) | O(n) | O(1) |
extract(),循環結束堆為空$copy = clone $heap; 或手動 extract() 存入陣列compare() 返回值:< 0 表示 $value1 優先級更高(在頂)strcmp)SplFixedArray 預分配底層存儲SPL Heap 提供標準庫級的堆實現,無需手寫二叉樹代碼,直接解決優先隊列、Top-K、中位數等經典算法問題。