PHP優先權佇列的介紹（附程式碼）

這篇文章帶給大家的內容是關於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優先權佇列的介紹（附程式碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！