PHP SplPriorityQueue 为什么取出顺序不稳定：同优先级元素的比较与排序验证

用 PHP 的 SplPriorityQueue 做任务调度时，最容易误判的一点是：给多个任务传入同一个优先级，并不意味着它们会按插入顺序取出。这个类底层是最大堆，优先级相同的节点在堆内没有稳定的先后保证；如果业务要求“同优先级先进先出”，就要把顺序号也纳入比较条件。

先看清 SplPriorityQueue 实际取出的是什么

我们用一组发布任务的场景写一段测试代码，三个任务都设置为相同的优先级10，代码没有对最终输出顺序做任何硬性断言：

setExtractFlags(SplPriorityQueue::EXTR_BOTH);

foreach (['compile', 'upload', 'notify'] as $job) {
    $queue->insert($job, 10);
}

while (!$queue->isEmpty()) {
    var_export($queue->extract());
    echo PHP_EOL;
}

每次结果都应是一组包含 data 和 priority 的数组，但 compile、upload、notify 的相对顺序不能作为业务契约。PHP 手册对 compare() 的说明也明确指出，同优先级元素会以不特定的顺序出队。

compare 返回值决定节点如何排进堆

SplPriorityQueue 默认是最大堆：比较时，第一个优先级更大，应返回正数；两者相等返回 0；第一个更小则返回负数。不要把这个方法理解成普通的“返回 true 就排前面”，它返回的是三态比较结果。

class MinPriorityQueue extends SplPriorityQueue
{
    public function compare(mixed $priority1, mixed $priority2): int
    {
        if ($priority1 === $priority2) {
            return 0;
        }

        return $priority1 > $priority2 ? -1 : 1;
    }
}

这个子类把较小数字视为更高优先级。若只是想查看排序，不建议一开始就重写 compare()；先用 EXTR_BOTH 检查数据和优先级是否在插入阶段就已经错了。

稳定顺序要把“先后”变成第二排序键

业务优先级相同的时候，可以把优先级包装成两个数字：第一个是业务优先级，第二个是插入时生成的单调序号。这里让较早进入队列的任务拥有更高的第二键，因此它会先出队。

class StablePriorityQueue extends SplPriorityQueue
{
    private int $sequence = 0;

    public function insert(mixed $value, int $priority): true
    {
        return parent::insert($value, [$priority, -$this->sequence++]);
    }

    public function compare(mixed $priority1, mixed $priority2): int
    {
        return $priority1  $priority2;
    }
}

$queue = new StablePriorityQueue();
$queue->insert('compile', 10);
$queue->insert('upload', 10);
$queue->insert('notify', 20);
$queue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

PHP底层比较数组时会先按顺序比对业务优先级，相等再比对序号。这里的负号很关键：SplPriorityQueue 默认的最大堆会优先取出数值更大的元素，插入越早的任务对应的负序号越接近0，同业务优先级下越早插入的元素自然会排在前面先出队。实际生产使用的代码要补充整数边界判断和序号溢出的处理，不要让序号无限制累加增长。

用可观察结果验收排序契约

测试不要只断言“队列非空”。至少检查三件事：高优先级是否先出队；同优先级是否按约定的序号出队；EXTR_BOTH 返回的优先级是否仍然包含完整的组合值。

$actual = [];
while (!$queue->isEmpty()) {
    $actual[] = $queue->extract()['data'];
}

if ($actual !== ['notify', 'compile', 'upload']) {
    throw new RuntimeException('priority queue order contract failed');
}

如果只需要数据，最后再切回默认的 EXTR_DATA。在迭代或复制队列做调试时也要留意：提取操作会消耗队列，验收脚本最好使用独立实例，避免调试代码改变业务队列。

常见误区与边界

• 把同优先级当成稳定队列：原生 SplPriorityQueue 没有这个保证。
• 重写 compare() 后忘记定义相等分支：返回值不完整会让边界行为难以解释。
• 直接比较混合类型优先级：业务优先级应统一为整数或结构一致的数组。
• 把 EXTR_BOTH 的数组当成业务数据：它包含 data 与 priority 两个键。

相关问题

SplPriorityQueue 是最大堆还是最小堆？

默认是最大堆，数值更大的优先级会先取出。要做最小堆，需要继承并重写 compare()。

怎样同时取出数据和优先级？

调用 setExtractFlags(SplPriorityQueue::EXTR_BOTH)，再从结果的 data 和 priority 字段读取。

同优先级任务能否保证先进先出？

不要依赖原生实现的默认顺序。把单调递增序号作为第二排序键，或是直接改用专门支持排序稳定性的队列实现即可。

总结

SplPriorityQueue 解决的是“按优先级快速取出”问题，不自动解决“同优先级按到达顺序处理”问题。先用 EXTR_BOTH 看清实际节点，再根据业务是否需要稳定性选择原生队列或带序号的比较策略，测试中同时覆盖高低优先级和相同优先级两条路径。