php堆实现
PHP 堆（Heap）实现方法
PHP 提供了多种方式实现堆数据结构，以下是常见方法：
使用 SplHeap 类
PHP 标准库（SPL）提供了 SplHeap 抽象类用于堆实现，需继承并实现 compare 方法：
class MyHeap extends SplHeap {
protected function compare($value1, $value2) {
return $value1 - $value2; // 最小堆实现
}
}
$heap = new MyHeap();
$heap->insert(4);
$heap->insert(8);
$heap->insert(1);
echo $heap->extract(); // 输出1（最小元素）使用 SplMinHeap/SplMaxHeap
SPL 还提供具体的最小堆和最大堆实现类：
$minHeap = new SplMinHeap();
$minHeap->insert(3);
$minHeap->insert(1);
echo $minHeap->extract(); // 输出1
$maxHeap = new SplMaxHeap();
$maxHeap->insert(3);
$maxHeap->insert(1);
echo $maxHeap->extract(); // 输出3数组模拟堆
可通过数组配合特定索引计算模拟堆结构：
function heapify(&$arr, $n, $i) {
$largest = $i;
$left = 2 * $i + 1;
$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) {
$swap = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $swap;
heapify($arr, $n, $largest);
}
}
function buildHeap(&$arr, $n) {
for ($i = floor($n / 2) - 1; $i >= 0; $i--)
heapify($arr, $n, $i);
}优先队列实现
结合 SplPriorityQueue 可实现带优先级的堆结构：
$pq = new SplPriorityQueue();
$pq->insert('Task 1', 3);
$pq->insert('Task 2', 1);
$pq->insert('Task 3', 2);
echo $pq->extract(); // 输出Task 1（最高优先级）性能比较
SplHeap系列类提供O(log n)的插入/删除复杂度- 数组模拟堆需要手动维护堆属性
- 优先队列适合需要关联优先级的场景
应用场景
- 任务调度系统
- 图算法（如Dijkstra）
- 数据流的中位数计算
- 游戏中的AI决策系统
对于需要自定义比较逻辑的场景，继承 SplHeap 是最灵活的方式；若只需简单数值比较，可直接使用 SplMinHeap 或 SplMaxHeap。
