php - 为什么 SplPriorityQueue 类是一个队列(概念)

Question

基本上 SplPriorityQueue 类是一个使用 max heap 算法的堆。

我不明白为什么在文档中应该是 prioritized queue，因为 queue 是一个 FIFO 集合(首先在, 先出) - 但是因为 SplPriorityQueue 它依赖于 priority variable 的比较功能，为什么它是一个队列？

为什么这个类不仅仅是一个SplPriorityCollection？!

-> SplPriorityQueue documentation

---

受 Mark Ba​​ker 评论的启发，我测试了当所有项目的优先级相同时比较函数的行为，结果证明具有相同优先级的集合不是 FIFO

$objPQ = new SplPriorityQueue(); 

$objPQ->insert('A', 1); 
$objPQ->insert('B', 1); 
$objPQ->insert('C', 1); 
$objPQ->insert('D', 1); 
$objPQ->insert('E', 1); 
$objPQ->insert('F', 1);
$objPQ->insert('G', 1);


foreach($objPQ as $val) {
    echo $val . "\n";
}

输出:

A G F E D C B

Answer 1

Basically SplPriorityQueue class is a heap using max heap algoritm [sic].

使用堆是一个实现细节，使用堆不是必需的。优先队列数据结构也不是 PHP 独有的(不是任何人说的那样!)。希望以下来自维基百科的简短引用会有所帮助:

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

– http://en.wikipedia.org/wiki/Priority_queue

---

同一来源也有以下说法:

If two elements have the same priority, they are served according to their order in the queue

这与 SplPriorityQueue 的作者在 PHP 错误报告 ([Won't Fix] Bug #53710 Data registered with equal priority not returned in expected order ) 中描述具有相同优先级值的迭代(错误)行为的评论相反。

There is no such guarantee. The only guarantee that you'll get from SplPriorityQueue is that you won't get an element out of order. Elements with the same priority are extracted in arbitrary order, the rest is implementation dependant.

上述错误报告的作者继续写了一篇博文，Taming SplPriorityQueue ，它使用以下技术强制执行可预测的队列顺序:

namespace Foo;

class SplPriorityQueue extends \SplPriorityQueue
{
    protected $queueOrder = PHP_INT_MAX;

    public function insert($datum, $priority)
    {
        if (is_int($priority)) {
            $priority = array($priority, $this->queueOrder--);
        }
        parent::insert($datum, $priority);
    }
}