## [SplPriorityQueue:優先隊列](https://www.php.net/manual/zh/class.splpriorityqueue.php#class.splpriorityqueue) >[info]優先隊列也是非常實用的一種數據結構，可以通過加權對值進行排序，由于排序在php內部實現，業務代碼中將精簡不少而且更高效。通過SplPriorityQueue::setExtractFlags(int $flag)設置提取方式可以提取數據（等同最大堆）、優先級、和兩者都提取的方式 SplPriorityQueue類提供了使用最大堆實現的優先級隊列的主要功能。 注意：具有相同優先級的元素的順序未定義。它可能與插入順序不同 SplPriorityQueue是以`Heap`：`堆`數據結構實現的，默認為`MaxHeap`模式，即`priority`越大越優先出隊，同時可以通過重寫`compare`方法來使用`MinHeap`（優先級越低越優先出隊，場景貌似很少吧） 理解：當我們出隊時會拿出`堆頂`的元素，此時`堆`的特性被破壞，`堆`會進行相應的調整至`穩定態`(`MaxHeap`or`MinHeap`)，即會將`最后`一個元素替換到`堆頂`，然后進行`穩定態`驗證，不符合堆特性則繼續調整，或者我們就得到了一個`穩定態`的`堆`，所以當優先級相同，出隊順序并不會按照入隊順序 SplPriorityQueue的入隊方法和出隊方法：insert和extract extract 出隊更為友好，即始終返回優先級最高的元素，優先級相投時會以堆調整的特性返回數據 >[danger] 注意，因為是`堆`實現，所以`rewind`方法是一個`no-op`沒有什作用的操作，因為`頭指針`始終指向`堆頂`，即`current`始終等于`top`，不像`List`只是游走指針，出隊是會刪除堆元素的，`extract`\=`current + next`（current出隊，從堆中刪除） ``` abstract SplHeap implements Iterator , Countable { /* 方法 */ public __construct ( void ) abstract protected compare ( mixed $value1 , mixed $value2 ) : int //比較元素，以便在篩選時將它們正確地放在堆中，如果value1大于value2則為正整數，如果相等則為0，否則為負整數 public count ( void ) : int //返回元素的個數 Countable? public current ( void ) : mixed //返回當前記錄節點索引的值 超出范圍返回空 Iterator public extract ( void ) : mixed //從堆頂部提取節點并進行篩選 public insert ( mixed $value ) : void //通過篩選將一個元素插入堆中 public isCorrupted ( void ) : bool //判斷堆是否處于損壞狀態 public isEmpty ( void ) : bool //檢查堆是否為空 public key ( void ) : mixed //返回當前節點索引 Iterator public next ( void ) : void //移動到下一個節點 Iterator public recoverFromCorruption ( void ) : void //從損壞的狀態恢復并允許堆上的進一步操作 public rewind ( void ) : void //將指針指向迭代開始處 Iterator public setExtractFlags ( int $flags ) : void //設置提取模式 public top ( void ) : mixed //返回堆頂部的節點 public valid ( void ) : bool //檢查堆是否還有節點 Iterator } ``` ## **例子：** ``` <?php $objPQ = new SplPriorityQueue(); $objPQ->insert('A',3); $objPQ->insert('B',6); $objPQ->insert('C',1); $objPQ->insert('D',2); echo "COUNT->".$objPQ->count()."<br>"; //mode of extraction /** * 設置元素出隊模式 * SplPriorityQueue::EXTR_DATA 僅提取值 * SplPriorityQueue::EXTR_PRIORITY 僅提取優先級 * SplPriorityQueue::EXTR_BOTH 提取數組包含值和優先級 */ $objPQ->setExtractFlags(SplPriorityQueue::EXTR_BOTH); //Go to TOP $objPQ->top(); //遍歷： while($objPQ->valid()){ print_r($objPQ->current()); echo "<br>"; $objPQ->next(); } output: COUNT->4 Array ( [data] => B [priority] => 6 ) Array ( [data] => A [priority] => 3 ) Array ( [data] => D [priority] => 2 ) Array ( [data] => C [priority] => 1 ) ?> ``` ## **例子：** ``` <?php class PQtest extends SplPriorityQueue { public function compare($priority1, $priority2) { //$priority1與優先級相同 3 6 ... if ($priority1 === $priority2) return 0; return $priority1 < $priority2 ? -1 : 1; // return $priority1 - $priority2;//高優先級優先 // return $priority2 - $priority1;//低優先級優先 } } $objPQ = new PQtest(); //$objPQ->insert('值',優先級); $objPQ->insert('A',3); $objPQ->insert('B',6); $objPQ->insert('C',1); $objPQ->insert('D',2); echo "COUNT->".$objPQ->count()."<br>"; /** * 設置元素出隊模式 * SplPriorityQueue::EXTR_DATA 僅提取值 * SplPriorityQueue::EXTR_PRIORITY 僅提取優先級 * SplPriorityQueue::EXTR_BOTH 提取數組包含值和優先級 */ $objPQ->setExtractFlags(PQtest::EXTR_BOTH); //Go to TOP $objPQ->top(); while($objPQ->valid()){ print_r($objPQ->current()); echo "<br>"; $objPQ->next(); } ?> output: COUNT->4 Array ( [data] => B [priority] => 6 ) Array ( [data] => A [priority] => 3 ) Array ( [data] => D [priority] => 2 ) Array ( [data] => C [priority] => 1 ) ```