PHP 優先級隊列：SplPriorityQueue

趙春朋發布于2019-07-01 12:37 / 3185人閱讀

摘要：迭代的話會刪除隊列元素指針始終指向所以沒什么意義出隊出隊更為友好，即始終返回優先級最高的元素，優先級相投時會以堆調整的特性返回數據。自定義優先級處理方式重寫方法定義自己的優先級處理機制。高優先級優先低優先級優先

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());
}

云服務器 GPU云服務器優先隊列 python優先隊列 SplPriorityQueue php 隊列功能

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31100.html

【SPL標準庫專題(7)】Datastructures：SplPriorityQueue

摘要：普通的隊列是一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭取出。在優先隊列中，元素被賦予優先級。當訪問元素時，具有最高優先級的元素最先取出。優先隊列具有最高級先出，的行為特征。普通的隊列是一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭取出。在優先隊列中，元素被賦予優先級。當訪問元素時，具有最高優先級的元素最先取出。優先隊列具有最高級先出（largest-in，first...

mindwind 2019-07-01 12:49 評論0 收藏0
Swoft 源碼解讀

摘要：官網源碼解讀號外號外歡迎大家我們開發組定了一個就線下聚一次的小目標里面的框架算是非常重的了這里的重先不具體到性能層面主要是框架的設計思想和框架集成的服務讓框架可以既可以快速解決很多問題又可以輕松擴展中的框架有在應該無出其右了這次解讀的源碼官網: https://www.swoft.org/源碼解讀: http://naotu.baidu.com/file/8... 號外號外, 歡迎大...

weij 2019-06-28 18:23 評論0 收藏0
Redis 實現隊列

摘要：場景說明用于處理比較耗時的請求，例如批量發送郵件，如果直接在網頁觸發執行發送，程序會出現超時高并發場景，當某個時刻請求瞬間增加時，可以把請求寫入到隊列，后臺在去處理這些請求搶購場景，先入先出的模式命令或往列表右側推入數據客戶端阻塞直到隊列有場景說明：用于處理比較耗時的請求，例如批量發送郵件，如果直接在網頁觸發執行發送，程序會出現超時高并發場景，當某個時刻請求瞬間增加時，可以把請...

PascalXie 2019-06-28 13:42 評論0 收藏0
Redis 實現隊列

摘要：場景說明用于處理比較耗時的請求，例如批量發送郵件，如果直接在網頁觸發執行發送，程序會出現超時高并發場景，當某個時刻請求瞬間增加時，可以把請求寫入到隊列，后臺在去處理這些請求搶購場景，先入先出的模式命令或往列表右側推入數據客戶端阻塞直到隊列有場景說明：用于處理比較耗時的請求，例如批量發送郵件，如果直接在網頁觸發執行發送，程序會出現超時高并發場景，當某個時刻請求瞬間增加時，可以把請...

LoftySoul 2019-07-30 14:38 評論0 收藏0