Einführung in die PHP-Prioritätswarteschlange (mit Code)

Dieser Artikel bietet Ihnen eine Einführung in die PHP-Prioritätswarteschlange (mit Code). Freunde in Not können darauf verweisen.

Die SPL-Bibliothek von PHP verfügt über eine integrierte SplPriorityQueue-Prioritätswarteschlange und wird mit der Heap-Datenstruktur implementiert. Der Standardwert ist der MaxHeap-Modus, d. h. je größer die Priorität, desto mehr Priorität erhält die Warteschlange. Gleichzeitig kann MinHeap verwendet werden, indem die Vergleichsmethode neu geschrieben wird (Je niedriger die Priorität, desto mehr Priorität wird dem Entfernen aus der Warteschlange eingeräumt, es scheint nur sehr wenige Szenarien zu geben).

SplPriorityQueue

Heap-Funktionen

Sie müssen hier aufpassen und verstehen: SplPriorityQueue ist als Heap-Datenstruktur implementiert. Wenn wir die Warteschlange entfernen, werden wir die Elemente herausnehmen Zu diesem Zeitpunkt werden die Eigenschaften des Heaps zerstört und der Heap wird entsprechend an den stabilen Zustand (MaxHeap oder MinHeap) angepasst, dh das letzte Element wird oben im Heap ersetzt , und dann wird die Überprüfung des stabilen Zustands durchgeführt, wenn die Eigenschaften des Heaps nicht erfüllt werden, oder wir Es wird ein stabiler Heap erhalten. Wenn die Prioritäten gleich sind, folgt die Reihenfolge der Entfernung aus der Warteschlange nicht der Warteschlange Befehl.

Quellcode-Beispiel:

<?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

Wie Sie sehen können, gibt die Warteschlange aufgrund der Merkmale keine Daten in der Reihenfolge zurück, in der sie in der Warteschlange stehen, obwohl die fünf Aufgaben die gleiche Priorität haben des Heaps:
1, Warteschlangenaufgabe1, Aufgabe2, Aufgabe3, Aufgabe4, Aufgabe5, da die Priorität gleich ist, befindet sich der Heap immer in einem stabilen Zustand.
2. Entfernen Sie die Warteschlange und rufen Sie Task1 ab. Passen Sie zunächst die Struktur an Task5, Task2, Task3 und Task4 an und erreichen Sie einen stabilen Zustand.
3. Entfernen Sie die Warteschlange und holen Sie sich Aufgabe 5. Der Stapel passt die Struktur zunächst an Aufgabe 4, Aufgabe 2 und Aufgabe 3 an und hat einen stabilen Zustand erreicht.
4. Nach dem Verlassen der Warteschlange wird der Heap zunächst an Task3 und Task2 angepasst und hat einen stabilen Zustand erreicht.
5. Entfernen Sie die Warteschlange und holen Sie sich Aufgabe3. Der Stapel passt die Struktur zunächst an Aufgabe2 an und hat einen stabilen Zustand erreicht.
4. Verlasse das Team und erhalte Aufgabe2.

Iterator, Countable

SplPriorityQueue implementiert die Schnittstelle Iterator, Countable, sodass wir sie mit der Funktion foreach/count bedienen oder die Methode rewind, valid, current, next/count verwenden können.

Beachten Sie, dass es sich bei der Rückspulmethode um eine No-Op-Operation handelt, die keine Auswirkungen hat, da es sich um eine Heap-Implementierung handelt, da der Kopfzeiger immer auf die Oberseite des Heaps zeigt, d. h. der aktuelle Wert ist immer gleich top, im Gegensatz zu List, bei dem es sich nur um einen wandernden Zeiger handelt, löscht die Warteschlange die Heap-Elemente, extract = current + next (aktuell wird aus der Warteschlange entfernt und aus dem Heap gelöscht).

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

Aus der Warteschlange extrahieren

Aus der Warteschlange extrahieren ist benutzerfreundlicher, das heißt, es gibt immer das Element mit der höchsten Priorität zurück mit der Heap-Anpassungsfunktion zurückgegeben.

<?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;
}

Benutzerdefinierte Prioritätsverarbeitungsmethode

Überschreiben Sie die Vergleichsmethode, um Ihren eigenen Prioritätsverarbeitungsmechanismus zu definieren.

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

Dieser Artikel ist hier zu Ende. Weitere spannende Inhalte finden Sie in der Spalte PHP-Video-Tutorial auf der chinesischen PHP-Website!

Das obige ist der detaillierte Inhalt vonEinführung in die PHP-Prioritätswarteschlange (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!