PHP 优先级队列：SplPriorityQueue

赵春朋发布于2019-07-01 12:37 / 3115人阅读

摘要：迭代的话会删除队列元素指针始终指向所以没什么意义出队出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。自定义优先级处理方式重写方法定义自己的优先级处理机制。高优先级优先低优先级优先

PHP 的 SPL 库内置了 SplPriorityQueue优先级队列，并且是以Heap数据结构实现的，默认为MaxHeap模式，即priority越大越优先出队，同时可以通过重写compare方法来使用MinHeap（优先级越低越优先出队，场景貌似很少吧）。

SplPriorityQueue 堆特性

这里需要注意并理解：SplPriorityQueue是以堆数据结构来实现的，当我们出队时会拿出堆顶的元素，此时堆的特性被破坏，堆会进行相应的调整至稳定态(MaxHeap or MinHeap)，即会将最后一个元素替换到堆顶，然后进行稳定态验证，不符合堆特性则继续调整，或者我们就得到了一个稳定态的堆，所以当优先级相同，出队顺序并不会按照入队顺序。

源码示例：

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出队，从堆中删除）。

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 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。

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方法定义自己的优先级处理机制。

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());
}

云服务器 GPU云服务器优先队列 python优先队列 SplPriorityQueue php 队列功能

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31100.html

【SPL标准库专题(7)】Datastructures：SplPriorityQueue

摘要：普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头取出。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先取出。优先队列具有最高级先出，的行为特征。普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头取出。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先取出。优先队列具有最高级先出（largest-in，first...

mindwind 2019-07-01 12:49 评论0 收藏0
Swoft 源码解读

摘要：官网源码解读号外号外欢迎大家我们开发组定了一个就线下聚一次的小目标里面的框架算是非常重的了这里的重先不具体到性能层面主要是框架的设计思想和框架集成的服务让框架可以既可以快速解决很多问题又可以轻松扩展中的框架有在应该无出其右了这次解读的源码官网: https://www.swoft.org/源码解读: http://naotu.baidu.com/file/8... 号外号外, 欢迎大...

weij 2019-06-28 18:23 评论0 收藏0
Redis 实现队列

摘要：场景说明用于处理比较耗时的请求，例如批量发送邮件，如果直接在网页触发执行发送，程序会出现超时高并发场景，当某个时刻请求瞬间增加时，可以把请求写入到队列，后台在去处理这些请求抢购场景，先入先出的模式命令或往列表右侧推入数据客户端阻塞直到队列有场景说明：用于处理比较耗时的请求，例如批量发送邮件，如果直接在网页触发执行发送，程序会出现超时高并发场景，当某个时刻请求瞬间增加时，可以把请...

PascalXie 2019-06-28 13:42 评论0 收藏0
Redis 实现队列

摘要：场景说明用于处理比较耗时的请求，例如批量发送邮件，如果直接在网页触发执行发送，程序会出现超时高并发场景，当某个时刻请求瞬间增加时，可以把请求写入到队列，后台在去处理这些请求抢购场景，先入先出的模式命令或往列表右侧推入数据客户端阻塞直到队列有场景说明：用于处理比较耗时的请求，例如批量发送邮件，如果直接在网页触发执行发送，程序会出现超时高并发场景，当某个时刻请求瞬间增加时，可以把请...

lifesimple 2019-08-16 10:45 评论0 收藏0
Redis 实现队列

摘要：场景说明用于处理比较耗时的请求，例如批量发送邮件，如果直接在网页触发执行发送，程序会出现超时高并发场景，当某个时刻请求瞬间增加时，可以把请求写入到队列，后台在去处理这些请求抢购场景，先入先出的模式命令或往列表右侧推入数据客户端阻塞直到队列有场景说明：用于处理比较耗时的请求，例如批量发送邮件，如果直接在网页触发执行发送，程序会出现超时高并发场景，当某个时刻请求瞬间增加时，可以把请...

LoftySoul 2019-07-30 14:38 评论0 收藏0