欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

PHP优先级队列的介绍(附代码)

程序员文章站 2022-03-16 15:37:21
...
本篇文章给大家带来的内容是关于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;

//执行结果
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出队,从堆中删除)。

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

<?php
class 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优先级队列的介绍(附代码)的详细内容,更多请关注其它相关文章!