大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章运用简单易懂的例子给大家介绍什么是PHP优先级队列,代码非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
10年积累的成都网站建设、成都网站设计经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站设计后付款的网站建设流程,更有长泰免费网站建设让你可以放心的选择与我们合作。
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()); }
关于什么是PHP优先级队列就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。