Signatur
Beschreibung
SplMinHeap ist eine konkrete Implementierung von SplHeap, die die abstrakte Methode compare() so definiert, dass das kleinste Element immer an der Spitze (Top) des Heaps steht. Sie eignet sich hervorragend für Prioritätswarteschlangen, bei denen niedrig priorisierte oder numerisch kleine Werte zuerst verarbeitet werden sollen.
Die Klasse implementiert die Interfaces Iterator, Countable und ArrayAccess (über SplHeap), wodurch sie mit foreach-Schleifen und anderen Standardkonstrukten kompatibel ist. Beim Iterieren über den Heap werden die Elemente in aufsteigender Reihenfolge aus dem Heap extrahiert – der Heap wird dabei geleert.
Typische Anwendungsfälle sind Dijkstra-Algorithmen, Task-Scheduler, bei denen die Aufgabe mit der niedrigsten Prioritätsnummer zuerst ausgeführt wird, oder das effiziente Ermitteln des kleinsten Elements aus einem sich dynamisch verändernden Datensatz. Die Zeitkomplexität für Einfügen und Entfernen beträgt O(log n).
Im Gegensatz zu einem sortierten Array bietet der Min-Heap den Vorteil, dass Einfüge- und Entnahmeoperationen deutlich effizienter sind, da keine vollständige Neusortierung stattfindet.
Beispiele
Grundlegende Verwendung eines Min-Heaps
<?php
$heap = new SplMinHeap();
$heap->insert(42);
$heap->insert(7);
$heap->insert(19);
$heap->insert(3);
$heap->insert(55);
echo 'Anzahl Elemente: ' . $heap->count() . PHP_EOL;
echo 'Kleinstes Element (top): ' . $heap->top() . PHP_EOL;
// Elemente der Reihe nach entnehmen (aufsteigend)
while (!$heap->isEmpty()) {
echo $heap->extract() . PHP_EOL;
}Min-Heap als einfache Prioritätswarteschlange
<?php
class Aufgabe {
public function __construct(
public readonly int $prioritaet,
public readonly string $name
) {}
}
$heap = new SplMinHeap();
$heap->insert(new Aufgabe(3, 'Bericht schreiben'));
$heap->insert(new Aufgabe(1, 'Server-Absturz beheben'));
$heap->insert(new Aufgabe(2, 'E-Mail beantworten'));
$heap->insert(new Aufgabe(1, 'Backup prüfen'));
// SplMinHeap vergleicht Objekte über compare() –
// für Objekte muss compare() überschrieben werden:
class AufgabenHeap extends SplMinHeap {
protected function compare(mixed $a, mixed $b): int {
// Kleinere Priorität = weiter oben => umgekehrte Rückgabe
return $b->prioritaet <=> $a->prioritaet;
}
}
$queue = new AufgabenHeap();
$queue->insert(new Aufgabe(3, 'Bericht schreiben'));
$queue->insert(new Aufgabe(1, 'Server-Absturz beheben'));
$queue->insert(new Aufgabe(2, 'E-Mail beantworten'));
$queue->insert(new Aufgabe(1, 'Backup prüfen'));
while (!$queue->isEmpty()) {
$aufgabe = $queue->extract();
echo "[Prio {$aufgabe->prioritaet}] {$aufgabe->name}" . PHP_EOL;
}Min-Heap mit foreach iterieren
<?php
$heap = new SplMinHeap();
foreach ([15, 3, 9, 1, 27, 6] as $zahl) {
$heap->insert($zahl);
}
// foreach extrahiert Elemente aufsteigend und leert den Heap!
foreach ($heap as $wert) {
echo $wert . ' ';
}
echo PHP_EOL;
echo 'Heap nach foreach leer: ' . ($heap->isEmpty() ? 'ja' : 'nein') . PHP_EOL;// Wichtig · Fallstricke
Vorsicht beim Iterieren: Das Durchlaufen eines SplMinHeap mit foreach verändert den Heap – jede Iteration ruft intern extract() auf, sodass der Heap am Ende leer ist. Soll der Heap erhalten bleiben, muss er zuvor geklont werden (clone $heap).
Objekte vergleichen: SplMinHeap::compare() nutzt standardmäßig den eingebauten PHP-Vergleich. Für komplexe Objekte sollte man SplMinHeap ableiten und compare() überschreiben, um das Vergleichskriterium explizit zu definieren. Die Methode muss einen negativen, nullen oder positiven Integer zurückgeben.
Korrupter Zustand: Wenn compare() eine Exception wirft, kann der Heap in einen inkonsistenten Zustand geraten. In diesem Fall ist nur noch recoverFromCorruption() hilfreich, um ihn wieder nutzbar zu machen.