PHP优先级队列的介绍（附代码）

内容导读

收集整理的这篇技术教程文章主要介绍了PHP优先级队列的介绍（附代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4295字，纯文字阅读大概需要7分钟。

内容图文

本篇文章给大家带来的内容是关于PHP优先级队列的介绍（附代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

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

SplPriorityQueue

堆特性

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

源码示例：

<?php$splPriorityQueue = new SplPriorityQueue();// 设定返回数据的meta信息// SplPriorityQueue::EXTR_DATA 默认 只返回数// SplPriorityQueue::EXTR_PRIORITY 只返回优先级// SplPriorityQueue::EXTR_BOTH 返回数据和优先级// $splPriorityQueue->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;//执行结果task1task5task4task3task2

可以看到，虽然 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出队，从堆中删除）。

<?php$splPriorityQueue = new SplPriorityQueue();$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;// 迭代的话会删除队列元素 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 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。

<?php$splPriorityQueue = new SplPriorityQueue();// data  priority$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());    echo $splPriorityQueue->count() . PHP_EOL;}

自定义优先级处理方式

重写compare方法定义自己的优先级处理机制。

<?phpclass CustomedSplPriorityQueue extends SplPriorityQueue{    public function compare($priority1, $priority2): int    {        // return $priority1 - $priority2;//高优先级优先        return $priority2 - $priority1;//低优先级优先    }}$splPriorityQueue = new CustomedSplPriorityQueue();$splPriorityQueue->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());}

本篇文章到这里就已经全部结束了，更多其他精彩内容可以关注PHP中文网的PHP视频教程栏目！

以上就是PHP优先级队列的介绍（附代码）的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的PHP优先级队列的介绍（附代码）全部内容，希望文章能够帮你解决PHP优先级队列的介绍（附代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。