SplPriorityQueue是PHP5.3的一个很棒的新特性。但是，在最近尝试在几个项目中使用它时，我遇到了一些(a)非直觉的行为，以及(b)在某些情况下至少是不希望出现的行为。在本文中，我将介绍我的解决方案。
关于堆和队列
队列是编程中的任何数据结构，当迭代时，它以“先进先出”(FIFO)的顺序返回值。对于“后进先出”(LIFO)迭代，您定义了一个堆栈。
堆是一种数据结构，其中给定一个特定节点，它下面的所有节点的值都小于它。（从技术上讲，这将被视为“最大堆”，因为您还可以有一个变体，其中所有子节点都具有更大的值；这称为“最小堆”。）
优先级队列是最大堆的特殊版本。通常，数据以特定的优先级注册——因此最大堆只查看优先级值，而不是数据本身。这允许以任何所需的顺序将数据插入队列，同时确保它们按照提供的优先级指定的顺序迭代。
PHP提供对应于每个的SPL数据结构：
- SplQueue，对应一个queue。
- SplStack，对应一个stack。
- SplHeap，
- SplMaxHeap，对应一个max-heap。
- SplMinHeap，对应一个min-heap。
- SplPriorityQueue，对应一个优先级队列。
问题
我遇到的第一个问题实际上是我的推理失误，即：
遍历堆会从堆中删除值。
遍历堆会从堆中删除值。
基本上，为了满足堆契约，即根节点始终是最大值（或最小值，在最小堆的情况下），任何先前的节点都必须被删除。
显然，这个问题是，如果您想多次遍历任何类型的堆，那么，您不能使用同一个实例。
我遇到的下一个问题是SplPriorityQueue：当具有相同优先级的项目入队时，这些项目的迭代顺序是……意外的。虽然文档指出“具有相同优先级的多个元素将以无特定顺序出列”，但事实是它是可预测的，并且不直观。例如，给定以下内容：
$queue->insert('foo', 1000);
$queue->insert('bar', 1000);
$queue->insert('baz', 1000);
$queue->insert('bat', 1000);
foreach ($queue as $data) echo $data, " ";
我期望“foobarbazbat”的结果，假设FIFO顺序（在queue中预期）具有相同的优先级；“foobazbatbar”，假设按数据排序（这可能在最大堆中是预期的）。事实上，两者都不正确：第一个项目将首先发出，然后以与入队时相反的顺序发出其余项目：“foobatbazbar”。
虽然这在某种程度上可以预见，但我发现我不想假设这样的顺序，也不想尝试围绕它编写代码。
解决方案
允许多次迭代
允许队列的多次迭代就像在迭代之前克隆队列一样简单：
foreach (clone $queue as $datum) echo $datum, " ";
问题在于自动化—在某些情况下，我不希望用户真的必须了解内部实现。
我对此的解决方案是使用内部和外部迭代器的想法。在这种特殊情况下，我创建了一个PriorityQueue类，它包含一个SplPriorityQueue实例，并且还实现了IteratorAggregate。这允许执行以下操作：
namespace Foo;
class PriorityQueue implements Countable, IteratorAggregate
{
protected $innerQueue;
public function __construct()
{
// I'll explain the lack of global namespacing later...
$this->innerQueue = new SplPriorityQueue;
}
public function count()
{
return count($this->innerQueue);
}
public function insert($datum, $priority)
{
$this->innerQueue->insert($datum, $priority);
}
public function getIterator()
{
return clone $this->innerQueue;
}
}
这种方法意味着当我使用PriorityQueue时，我可以确信我可以计算并迭代它……一次又一次。
我在代码注释中提到我没有将SplPriorityQueue导入命名空间。原因是我还想解决可预测队列顺序的问题。
执行可预测的队列顺序
等优先级队列顺序问题的求解其实很简单。虽然我在SplPriorityQueue::compare手册页上找到了它，但MatthewTurland还在SPL的演示文稿中讨论了它，它取决于一个简单的事实：优先级不需要是整数。
这是什么意思？这意味着以下是不等价的，并且会导致更符合预期的排序顺序：
$queue->insert('foo', array(1000, 1000));
$queue->insert('bar', array(1000, 100));
$queue->insert('baz', array(1000, 10));
$queue->insert('bat', array(1000, 1));
foreach ($queue as $data) echo $data, " ";
这会导致“foobarbazbat”！
那么，诀窍就是自动化解决方案。我在自定义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);
}
}
当每个数据被添加到队列中时，如果优先级是一个整数，它会将其包装在一个数组中，使用$queueOrder作为数组的第二个值，并递减$queueOrder完成。然后使用新的优先级来插入值。
使用此扩展可确保优先级队列中的顺序现在是可预测的。
结论
SplPriorityQueue确实很强大，它为我节省了大量的编程时间——而且在使用更大的数据集时还可能节省CPU进程和内存。虽然它可能并不总能满足我的用例，但事实是，尤其是在命名空间可用的情况下，我可以轻松地覆盖该类以满足我的需要。
