Ds\PriorityQueue — Klasse · PHP-Referenz

Signatur

class Ds\PriorityQueue implements Ds\Collection

Beschreibung

Ds\PriorityQueue ist eine Datenstruktur aus der Data Structures-Erweiterung (ext-ds), die Elemente zusammen mit einer ganzzahligen Priorität speichert. Beim Abrufen wird stets das Element mit der höchsten Priorität zuerst zurückgegeben (Max-Heap-Semantik). Bei gleicher Priorität wird die Einfügereihenfolge berücksichtigt (FIFO innerhalb der gleichen Prioritätsstufe).

Gegenüber SplPriorityQueue bietet Ds\PriorityQueue eine sauberere API, vorhersehbares Verhalten bei Prioritätsgleichheit sowie eine besonders speicher- und laufzeiteffiziente interne Implementierung als binärer Heap. Sie ist besonders nützlich für Aufgaben wie Aufgabenplanung, Ereignisverarbeitung oder Dijkstra-Algorithmen.

Die Klasse implementiert das Ds\Collection-Interface und bietet damit Methoden wie count(), isEmpty(), copy() und toArray(). Wichtig: PriorityQueue ist nicht direkt iterierbar ohne Elemente zu entnehmen — beim Iterieren werden Elemente in Prioritätsreihenfolge aus der Warteschlange entfernt.

push(mixed $value, int $priority): Fügt ein Element mit Priorität hinzu.
pop(): mixed: Entfernt und gibt das Element höchster Priorität zurück.
peek(): mixed: Gibt das Element höchster Priorität zurück, ohne es zu entfernen.
count(): int: Gibt die Anzahl der Elemente zurück.
isEmpty(): bool: Prüft, ob die Warteschlange leer ist.
copy(): Ds\PriorityQueue: Erstellt eine flache Kopie.
toArray(): array: Gibt alle Elemente als Array zurück (in Prioritätsreihenfolge, zerstörerisch).

Beispiele

Aufgaben nach Priorität verarbeiten

<?php
require 'vendor/autoload.php'; // oder PECL-Extension laden

$queue = new Ds\PriorityQueue();

$queue->push('Niedrig-Prio-Aufgabe', 1);
$queue->push('Hoch-Prio-Aufgabe',   10);
$queue->push('Mittel-Prio-Aufgabe',  5);
$queue->push('Kritische Aufgabe',   20);

echo 'Elemente in der Warteschlange: ' . $queue->count() . PHP_EOL;
echo 'Nächste Aufgabe (peek): ' . $queue->peek() . PHP_EOL;

while (!$queue->isEmpty()) {
    echo 'Verarbeite: ' . $queue->pop() . PHP_EOL;
}

Elemente in der Warteschlange: 4 Nächste Aufgabe (peek): Kritische Aufgabe Verarbeite: Kritische Aufgabe Verarbeite: Hoch-Prio-Aufgabe Verarbeite: Mittel-Prio-Aufgabe Verarbeite: Niedrig-Prio-Aufgabe

FIFO-Verhalten bei gleicher Priorität

<?php
$queue = new Ds\PriorityQueue();

$queue->push('Erster',  5);
$queue->push('Zweiter', 5);
$queue->push('Dritter', 5);

// Bei gleicher Priorität bleibt die Einfügereihenfolge erhalten
while (!$queue->isEmpty()) {
    echo $queue->pop() . PHP_EOL;
}

Erster Zweiter Dritter

Kopie verwenden, um die Queue zu inspizieren ohne sie zu zerstören

<?php
$queue = new Ds\PriorityQueue();
$queue->push('A', 3);
$queue->push('B', 1);
$queue->push('C', 2);

// Kopie erstellen, damit das Original erhalten bleibt
$copy = $queue->copy();

echo 'Reihenfolge nach Priorität:' . PHP_EOL;
while (!$copy->isEmpty()) {
    echo $copy->pop() . PHP_EOL;
}

echo 'Originalgröße: ' . $queue->count() . PHP_EOL;

Reihenfolge nach Priorität: A C B Originalgröße: 3

// Wichtig · Fallstricke

Voraussetzung: Die Ds-Erweiterung ist keine PHP-Kern-Extension und muss separat installiert werden: pecl install ds oder über Composer (composer require php-ds/php-ds für einen Polyfill).

Achtung bei toArray(): Diese Methode ist zerstörerisch — sie entnimmt alle Elemente in Prioritätsreihenfolge und lässt eine leere Queue zurück. Für eine nicht-zerstörerische Inspektion immer copy()->toArray() verwenden.

Vergleich mit SplPriorityQueue: Im Gegensatz zu SplPriorityQueue verhält sich Ds\PriorityQueue bei gleichen Prioritäten deterministisch (FIFO). SplPriorityQueue hat hier undefiniertes Verhalten.

Negative Prioritäten sind erlaubt und können sinnvoll eingesetzt werden, um explizit niedrig priorisierte Elemente zu markieren.

Siehe auch

Ds\Queue Ds\Deque Ds\Collection SplPriorityQueue