SplPriorityQueue - 优先队列

Last updated 5 years ago

Was this helpful?

SplPriorityQueue - 优先队列

SplPriorityQueue是基于堆实现的.

SplQueue(队列)类就是实现队列操作，和栈一样，它也可以继承双链表(SplDoublyLinkedList)轻松实现。

优先队列也是非常实用的一种数据结构，可以通过加权对值进行排序，由于排序在php内部实现，业务代码中将精简不少而且更高效。通过SplPriorityQueue::setExtractFlags(int $flag)设置提取方式可以提取数据（等同最大堆）、优先级、和两者都提取的方式。

类摘要

SplPriorityQueue implements Iterator , Countable {
    public __construct ( void )
    public int compare ( mixed $priority1 , mixed $priority2 ) // 比较优先级，以便在筛选时将元素正确放置在堆中。
    public int count ( void ) // 计算队列中元素的数量。
    public mixed current ( void ) // 返回迭代器指向的当前节点
    public mixed extract ( void ) // 从堆顶部提取一个节点并向上移动
    public void insert ( mixed $value , mixed $priority ) // 在队列中插入一个元素
    public bool isEmpty ( void ) //检查队列是否为空。
    public mixed key ( void ) // 返回当前节点索引(key键)
    public void next ( void ) // 移动到下一个节点
    public void recoverFromCorruption ( void ) // 从损坏的状态恢复，并允许队列中的其他操作。
    public void rewind ( void ) // 将迭代器倒回起始
    public void setExtractFlags ( int $flags ) // 设置提取模式
    public mixed top ( void ) // 从队列顶部的节点上看一眼
    public bool valid ( void ) // 检查队列是否包含多个节点。
}

可以看到SplPriorityQueue实现了Iterator（迭代器）

其中：compare方法比较时：

priority1 > priority2 ,返回1
priority1 = priority2 ,返回0
priority1 < priority2 ,返回-1

注意：通过extract,next方法操作，rewind 没用回到当初的队列起始位置

简单示例：

$pq = new SplPriorityQueue();

$pq->insert('a', 10);
$pq->insert('b', 1);
$pq->insert('c', 8);
$pq->insert('d', 3);

echo $pq->count() .PHP_EOL; //4
echo $pq->current() . PHP_EOL; //a
echo $pq->current() . PHP_EOL; //a 因为迭代器的指针没用移动
echo $pq->next() . PHP_EOL;  //迭代器移动会影响到ｗhile的输出
echo $pq->current() . PHP_EOL; //c 
echo $pq->compare(10, 1) . PHP_EOL; //1  对优先级的数值进行比较
//echo $pq->extract() . PHP_EOL; // c
//echo $pq->extract() . PHP_EOL; // d ,注意迭代器的指针发生了变化，会影响到ｗhile的输出
//echo $pq->top() . PHP_EOL;  // b,extract操作导致指针已经移动将d扔出，所以此处队列的顶端是b

/**
 * 设置元素出队模式
 * SplPriorityQueue::EXTR_DATA 仅提取值
 * SplPriorityQueue::EXTR_PRIORITY 仅提取优先级
 * SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级
 */
echo "while:" . PHP_EOL;
$pq->rewind();
$pq->setExtractFlags(SplPriorityQueue::EXTR_DATA);
//$pq->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
//$pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

while($pq->valid()) {
    echo 'key:' . $pq->key() . PHP_EOL; // 3 2 1 0 
    print_r($pq->current()). PHP_EOL;//a c d b
    $pq->next();
}

上面输出结果：

1.EXTR_DATA 仅提取值, 则输出：a c b
2.EXTR_PRIORITY 仅提取优先级, 则输出：10 8 1
3.EXTR_BOTH 提取数组包含值和优先级, 则输出：Array ( [data] => a [priority] => 10 ) Array ( [data] => c [priority] => 8 ) Array ( [data] => b [priority] => 1 )

资料

这方面zendframework的底层有所重写实现，可以参考

Previous数据结构 NextSplQueue - 队列