PHP 优先级队列：SplPriorityQueue

PHP 的 SPL 库内置了 SplPriorityQueue 优先级队列，是以 Heap 堆特性实现的，默认为 MaxHeap 模式，即 priority 越大越优先出队，同时可以通过重写 compare 方法来使用 MinHeap（优先级越低越优先出队，场景貌似很少吧）。
SplPriorityQueue
堆特性
这里需要注意并理解：SplPriorityQueue 是以堆数据结构来实现的，当我们出队时会拿出堆顶的元素，此时堆的特性被破坏，堆会进行相应的调整至稳定态 (MaxHeap or MinHeap)，即会将最后一个元素替换到堆顶，然后进行稳定态验证，不符合堆特性则继续调整，或者我们就得到了一个稳定态的堆，所以当优先级相同，出队顺序并不会按照入队顺序。
源码示例：
<?php
$splPriorityQueue = new \SplPriorityQueue();
// 设定返回数据的 meta 信息
// \SplPriorityQueue::EXTR_DATA 默认 只返回数
// \SplPriorityQueue::EXTR_PRIORITY 只返回优先级
// \SplPriorityQueue::EXTR_BOTH 返回数据和优先级
// $splPriorityQueue->setExtractFlags(\SplPriorityQueue::EXTR_DATA);
$splPriorityQueue->insert(“task1”, 1);
$splPriorityQueue->insert(“task2”, 1);
$splPriorityQueue->insert(“task3”, 1);
$splPriorityQueue->insert(“task4”, 1);
$splPriorityQueue->insert(“task5”, 1);

echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;

// 执行结果
task1
task5
task4
task3
task2
可以看到，虽然 5 个任务的优先级相同，但队列并没有按照入队顺序返回数据，因为堆的特性使然：1、入队 task1, task2, task3, task4, task5，因为优先级相同，所以堆一直处于稳定态。2、出队，得 task1，堆先将结构调整为 task5, task2, task3, task4，已然达到了稳定态。3、出队，得 task5，堆先将结构调整为 task4, task2, task3，已然达到了稳定态。4、出队，得 task4，堆先将结构调整为 task3, task2，已然达到了稳定态。5、出队，得 task3，堆先将结构调整为 task2，已然达到了稳定态。4、出队，得 task2。
Iterator, Countable
SplPriorityQueue 实现了 Iterator, Countable 接口，所以我们可以 foreach/count 函数操作它，或者使用 rewind,valid,current,next/count 方法。
注意，因为是堆实现，所以 rewind 方法是一个 no-op 没有什作用的操作，因为头指针始终指向堆顶，即 current 始终等于 top，不像 List 只是游走指针，出队是会删除堆元素的，extract = current + next（current 出队，从堆中删除）。
<?php
$splPriorityQueue = new \SplPriorityQueue();

$splPriorityQueue->insert(“task1”, 1);
$splPriorityQueue->insert(“task2”, 2);
$splPriorityQueue->insert(“task3”, 1);
$splPriorityQueue->insert(“task4”, 4);
$splPriorityQueue->insert(“task5”, 5);

echo “Countable：” . count($splPriorityQueue) . PHP_EOL;

// 迭代的话会删除队列元素 current 指针始终指向 top 所以 rewind 没什么意义
for ($splPriorityQueue->rewind(); $splPriorityQueue->valid();$splPriorityQueue->next()) {
var_dump($splPriorityQueue->current());
var_dump($splPriorityQueue->count());
$splPriorityQueue->rewind();
}

var_dump(“is empty:” . $splPriorityQueue->isEmpty());
Extract 出队
extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。
<?php
$splPriorityQueue = new \SplPriorityQueue();

// data priority
$splPriorityQueue->insert(“task1”, 1);
$splPriorityQueue->insert(“task2”, 2);
$splPriorityQueue->insert(“task3”, 1);
$splPriorityQueue->insert(“task4”, 4);
$splPriorityQueue->insert(“task5”, 5);

echo “Countable：” . count($splPriorityQueue) . PHP_EOL;

while (! $splPriorityQueue->isEmpty()) {
var_dump($splPriorityQueue->extract());
echo $splPriorityQueue->count() . PHP_EOL;
}
自定义优先级处理方式
重写 compare 方法定义自己的优先级处理机制。
<?php
class CustomedSplPriorityQueue extends SplPriorityQueue
{
public function compare($priority1, $priority2): int
{
// return $priority1 – $priority2;// 高优先级优先
return $priority2 – $priority1;// 低优先级优先
}
}

$splPriorityQueue = new \CustomedSplPriorityQueue();
$splPriorityQueue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$splPriorityQueue->insert(“task1”, 1);
$splPriorityQueue->insert(“task2”, 2);
$splPriorityQueue->insert(“task3”, 1);
$splPriorityQueue->insert(“task4”, 4);
$splPriorityQueue->insert(“task5”, 5);

echo “Countable：” . count($splPriorityQueue) . PHP_EOL;

while (!$splPriorityQueue->isEmpty()) {
var_dump($splPriorityQueue->extract());
}