Почему класс SplPriorityQueue представляет собой очередь (концептуальный)

Question

В основном SplPriorityQueue класс - это куча, используя max heap algoritm.

Я не понимаю, почему в документации должна быть 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 

Answer 1

в основном SplPriorityQueue класс представляет собой кучу с помощью max heap АЛГОРИТМА [так в оригинале].

Тот факт, что куча используется это подробно реализация, используя кучу не является обязательным требованием. Структура данных очереди приоритетов также не уникальна для 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); 
    } 
} 

Answer 2

SPLPriorityQueue-видимому, действует скорее как Heap, чем очереди, аспект 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(); 
}