爲什麼SplPriorityQueue類是一個隊列（概念上）

基本上SplPriorityQueue類是一個堆使用max heap算法。爲什麼SplPriorityQueue類是一個隊列（概念上）

我不明白爲什麼在文件被認爲是一個prioritized queue，因爲queue是FIFO集合（先入先出） - 而是因爲它SplPriorityQueue比較函數依賴的priority variable，爲什麼它是一個隊列？

爲什麼這個班不只是一個SplPriorityCollection？！

- >SplPriorityQueue documentation

通過馬克·貝克評論啓發我測試比較功能的行爲時，優先級是所有項目一樣，它竟然具有相同的優先級集合不一個FIFO

$objPQ = new SplPriorityQueue(); 

$objPQ->insert('A', 1); 
$objPQ->insert('B', 1); 
$objPQ->insert('C', 1); 
$objPQ->insert('D', 1); 
$objPQ->insert('E', 1); 
$objPQ->insert('F', 1); 
$objPQ->insert('G', 1); 


foreach($objPQ as $val) { 
    echo $val . "\n"; 
}

輸出：

A G F E D C B

來源

2014-08-27 Cristian Bitoi

因爲（除非您指定不同的優先級）它是先進先出......並且在大多數情況下，您將爲所有事物指定相同的優先級... PriorityQueue和隊列之間的區別在於，您___擁有選項_以優先處理條目，以便某些___可以在其他人之前處理 – 2014-08-27 09:03:21

Thx 。我進行了測試，並且具有相同的優先級並不像FIFO。查看我編輯的問題。這是非常好的一點，我沒有這樣想，但它不適用。 – 2014-08-27 09:15:44

在這種情況下，您可能已經發現了一個錯誤：對於一個隊列，行爲應該如我所描述的....否則，您可能只是使用splheap – 2014-08-27 10:22:14

使用的值基本上SplPriorityQueue類是使用max heap algoritm [原文如此]堆。

的事實是，用於堆是實現細節，使用堆不是必要條件。優先隊列數據結構並不是PHP所獨有的（不是任何人都說它是！）。希望以下維基百科的簡短引用將對您有所幫助：

雖然優先級隊列通常使用堆實現，但它們在概念上與堆不同。優先級隊列是一個抽象概念，如「一個列表」或「一個地圖」;就像列表可以用鏈表或數組實現一樣，優先級隊列可以用堆或其他各種方法實現，例如無序數組。

- http://en.wikipedia.org/wiki/Priority_queue

同一消息來源還具有以下的說：

如果兩個元素具有相同的優先級，他們根據自己在隊列
順序供應

這與SplPriorityQueue作者的評論相反PHP錯誤報告（[Won't Fix] Bug #53710 Data registered with equal priority not returned in expected order）描述具有相同優先級值的迭代（錯誤）行爲。

有沒有這樣的保證。從 SplPriorityQueue獲得的唯一保證是您不會無法獲得元素。元素與相同的優先級以任意順序提取，其餘爲依賴的實現。

上述錯誤報告的作者接着寫了一篇博客文章，Taming SplPriorityQueue，它擊中使用以下方法執行一個可預見的隊列順序：

namespace Foo; 

class SplPriorityQueue extends \SplPriorityQueue 
{ 
    protected $queueOrder = PHP_INT_MAX; 

    public function insert($datum, $priority) 
    { 
     if (is_int($priority)) { 
      $priority = array($priority, $this->queueOrder--); 
     } 
     parent::insert($datum, $priority); 
    } 
}

來源

2014-08-27 19:49:48 salathe

Thx。引人注目的是你給出的文件迴應。 – 2014-08-28 00:00:11

簡而言之，我在閱讀文檔（維基百科，手冊，錯誤報告）後瞭解到，「優先級隊列」是一個與「隊列」不同的抽象概念。糾正我，如果我錯了。 – 2014-08-28 00:03:13

只是澄清，$ priority = array（$ priority，$ this-> queueOrder--）;做？ – kosinix 2016-05-27 13:32:30

SPLPriorityQueue似乎更像一個堆比隊列，應當用於爲它是一個隊列不施加

然而FIFO方面，FIFO可以通過修改所述插入件被恢復調整在比較功能

class PQtest extends SplPriorityQueue 
{ 
    protected $serial = PHP_INT_MAX; 

    public function insert($value, $priority) { 
     parent::insert($value, array($priority, $this->serial--)); 
    } 

    public function compare($priority1, $priority2) 
    { 
     if ($priority1 === $priority2) return 0; 
     return $priority1 < $priority2 ? -1 : 1; 
    } 
} 

$objPQ = new PQtest(); 

$objPQ->insert('A',1); 
$objPQ->insert('B',1); 
$objPQ->insert('C',1); 
$objPQ->insert('D',1); 
$objPQ->insert('E',1); 
$objPQ->insert('F',1); 

echo "COUNT->".$objPQ->count().PHP_EOL; 

//mode of extraction 
$objPQ->setExtractFlags(PQtest::EXTR_BOTH); 

//Go to TOP 
$objPQ->top(); 

while($objPQ->valid()){ 
    print_r($objPQ->current()); 
    echo PHP_EOL; 
    $objPQ->next(); 
}

來源

2014-08-27 10:44:21

Txh。智能方式強制執行FIFO原則覆蓋插入方法。 +1 – 2014-08-28 00:09:20

爲什麼SplPriorityQueue類是一個隊列（概念上）

回答

相關問題