PHP优先级行列的引见（附代码）【php教程】,php,spl,queue,priority-queue

本篇文章给人人带来的内容是关于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());
}

本篇文章到这里就已悉数完毕了，更多其他精彩内容能够关注ki4网的PHP视频教程栏目！

以上就是PHP优先级行列的引见（附代码）的细致内容，更多请关注ki4网别的相干文章！