Die Startseite eines Shops soll die zehn größten Bestellungen des Tages zeigen. Jede neue Bestellung kommt ins Array, das Skript sortiert alles neu und schneidet zehn Einträge ab. Bei ein paar hundert Bestellungen merkt das niemand, bei einer Million schon. Für genau diese Aufgabe gibt es den Heap. Wie Stapel und Warteschlangen funktionieren, bei denen zählt, wer zuletzt oder zuerst kam, zeigt das Tutorial zu SplStack. Ein PHP Heap fragt nicht nach der Ankunft. Er gibt immer das kleinste, das größte oder das wichtigste Element zuerst heraus. Wer mit dem Begriff den Arbeitsspeicher meint, findet am Ende einen kurzen Abschnitt dazu.
Alle Beispiele ergaben unter Windows und Linux mit PHP 8.4 dieselbe Ausgabe. Wo andere Versionen abweichen, steht es dabei.
Was ein Heap in PHP ist: ein Baum im Array
Ein PHP Heap ist ein Binärbaum mit einer einzigen Regel. Beim Min-Heap ist jeder Knoten kleiner oder gleich seinen Kindern, oben steht also immer das kleinste Element. Beim Max-Heap ist es umgekehrt. Geschwister untereinander sind nicht sortiert. Der Baum füllt sich Ebene für Ebene von links nach rechts. Deshalb braucht PHP keine Zeiger zwischen den Knoten, sondern legt alles in ein gewöhnliches Array: Die Kinder des Elements an Index i liegen bei 2i+1 und 2i+2. Einfügen und Entnehmen bewegen einen Wert nur entlang eines Pfades, bei einer Million Einträgen sind das rund zwanzig Schritte.
<?php
$heap = new SplMinHeap();
foreach ([5, 1, 8, 3, 9, 2] as $zahl) {
$heap->insert($zahl);
}
var_dump($heap);
/* im privaten Feld "heap" steht das Array
1, 3, 2, 5, 9, 8 */
Dieses Array ist nicht sortiert, erfüllt aber die Regel. Als Baum gezeichnet sieht man, warum:
flowchart TD
A[1 an Index 0] --> B[3 an Index 1]
A --> C[2 an Index 2]
B --> D[5 an Index 3]
B --> E[9 an Index 4]
C --> F[8 an Index 5]
Syntax im Original: SplHeap und SplPriorityQueue
Drei fertige Heaps bringt PHP mit, zwei davon erben von der abstrakten Klasse SplHeap:
abstract class SplHeap
implements Iterator, Countable
{
public insert(mixed $value): true
public extract(): mixed
public top(): mixed
public count(): int
public isEmpty(): bool
public isCorrupted(): bool
public recoverFromCorruption(): true
abstract protected compare(
mixed $value1,
mixed $value2
): int
}
class SplMinHeap extends SplHeap {}
class SplMaxHeap extends SplHeap {}
class SplPriorityQueue
implements Iterator, Countable
{
public insert(
mixed $value,
mixed $priority
): true
public setExtractFlags(int $flags): int
public compare(
mixed $priority1,
mixed $priority2
): int
}
/* A heap is a tree-based data structure: the
value at the top of the heap is the smallest
(SplMinHeap) or the maximum (SplMaxHeap).
insert() adds a value and restores the order,
extract() removes the top, top() only reads it.
compare() returns a positive integer if value1
belongs closer to the top than value2.
Iterating a heap with foreach removes the
elements. In SplPriorityQueue the highest
priority comes first; elements with the same
priority come out in no particular order.
Extract flags: EXTR_DATA, EXTR_PRIORITY,
EXTR_BOTH. On an empty heap extract() and
top() throw a RuntimeException. */
Wichtig ist die Zeile zu compare(): Ein positiver Wert bedeutet, dass der erste Wert weiter nach oben gehört. SplPriorityQueue arbeitet intern genauso, speichert aber zu jedem Wert eine eigene Priorität.
SplMinHeap und SplMaxHeap im Einsatz
Für Zahlen oder Strings genügen die beiden fertigen Klassen. insert() legt einen Wert hinein, extract() nimmt das oberste Element heraus, top() schaut nur nach:
<?php
$max = new SplMaxHeap();
foreach ([5, 1, 8, 3, 9, 2] as $zahl) {
$max->insert($zahl);
}
echo $max->top(), ' / ', count($max), "\n";
/* 9 / 6, top() entfernt nichts */
while (!$max->isEmpty()) {
echo $max->extract(), ' ';
}
/* 9 8 5 3 2 1 */
Mit SplMinHeap kommt dieselbe Liste als 1, 2, 3, 5, 8, 9 heraus. Verglichen wird wie mit den Operatoren < und >. Bei Strings heißt das Byte-Reihenfolge: Apfel, Birne und Zitrone standen im Test vor apfel und banane, weil Großbuchstaben kleinere Bytewerte haben. Numerische Strings wie '10' und '9' vergleicht PHP dagegen als Zahlen. Auch Arrays lassen sich einfügen, mit einer Überraschung: Das kürzere Array gilt als kleiner. [0, 'x', 'extra'] landete im Min-Heap hinter [3, 'c'], weil es drei Elemente hat.
Heaps durchlaufen: foreach leert den Heap
Wer einen PHP Heap zur Kontrolle ausgibt und danach weiterarbeiten will, steht vor einem leeren Objekt. Jeder Schritt einer foreach-Schleife entnimmt das oberste Element:
<?php
$heap = new SplMinHeap();
foreach ([4, 2, 7] as $zahl) {
$heap->insert($zahl);
}
foreach (clone $heap as $wert) {
echo $wert, ' ';
}
/* 2 4 7 */
echo "\n", count($heap), "\n";
/* 3, das Original bleibt voll */
foreach ($heap as $schluessel => $wert) {
echo "$schluessel:$wert ";
}
/* 2:2 1:4 0:7 */
echo "\n", count($heap);
/* 0 */
Die Schlüssel zählen rückwärts. Ein clone vor der Schleife schont das Original, einen Iteratormodus wie bei SplStack gibt es nicht.
Gefährlich wird es, wenn die Schleife selbst etwas in den PHP Heap einfügt. foreach liest das oberste Element und entnimmt beim nächsten Schritt das, was dann oben liegt. Wurde im Test bei Wert 2 einmalig eine 1 eingefügt, lautete die Ausgabe 2 2 4 7: Die 2 erschien doppelt, die 1 wurde still entnommen und nie ausgegeben. Wer bei jedem Durchlauf mit Wert 2 eine 1 nachschiebt, baut eine Endlosschleife. Legt die Verarbeitung unterwegs neue Elemente nach, ist while (!$heap->isEmpty()) mit extract() der sichere Weg.
Eigene Heaps mit compare(): das Vorzeichen
Für Datensätze, Objekte oder eigene Regeln erweitert man SplHeap und schreibt compare(). Dort steckt die häufigste Falle. Wer vom Sortieren mit usort() kommt, schreibt aus Gewohnheit:
<?php
class Aufsteigend extends SplHeap
{
protected function compare(
mixed $a,
mixed $b
): int {
return $a <=> $b;
}
}
$heap = new Aufsteigend();
foreach ([5, 1, 8, 3] as $zahl) {
$heap->insert($zahl);
}
foreach ($heap as $wert) {
echo $wert, ' ';
}
/* 8 5 3 1, also absteigend */
Beim Callback von usort() ergibt $a <=> $b eine aufsteigende Liste. In einem PHP Heap bedeutet ein positiver Wert aber „weiter nach oben“, und damit kommt das größte Element zuerst. Für einen Heap, der den günstigsten Artikel zuerst liefert, werden die Operanden getauscht:
<?php
class GuenstigsteZuerst extends SplHeap
{
protected function compare(
mixed $a,
mixed $b
): int {
return $b['preis'] <=> $a['preis'];
}
}
$heap = new GuenstigsteZuerst();
$heap->insert(['name' => 'A', 'preis' => 9.9]);
$heap->insert(['name' => 'B', 'preis' => 2.5]);
$heap->insert(['name' => 'C', 'preis' => 5.0]);
echo $heap->extract()['name'];
/* B */
Zwei andere Rückgaben gehen ohne declare(strict_types=1) schief, ohne dass PHP abbricht. return $a > $b; liefert einen Wahrheitswert und machte im Test aus 5, 1, 8, 3, 9, 2, 7 die wirre Folge 5, 7, 2, 9, 3, 8, 1. return $a - $b; erzeugte bei Preisen wie 0.5, 0.2 und 0.9 Deprecated: Implicit conversion from float 0.3 to int loses precision und die falsche Reihenfolge 0.5, 0.9, 0.2. Mit strict_types enden beide sofort in einem TypeError, etwa Return value must be of type int, true returned. Der Raumschiff-Operator <=> ist deshalb die einzige Form, die man sich angewöhnen sollte.
SplPriorityQueue: Daten mit Priorität
Die SplPriorityQueue ist ein PHP Heap, bei dem Wert und Priorität getrennt stehen. Die höchste Priorität kommt zuerst, so wie Eilaufträge vorgehen. Schwieriger ist die Frage, was bei gleicher Priorität passiert:
<?php
$queue = new SplPriorityQueue();
foreach (range('A', 'J') as $auftrag) {
$queue->insert($auftrag, 1);
}
while ($queue->valid()) {
echo $queue->extract();
}
/* AJIHGFEDCB */
Der erste Auftrag kommt zuerst, alle anderen in umgekehrter Reihenfolge. Dasselbe Ergebnis lieferten PHP 8.2, 8.3, 8.4 und 8.5. Verlassen sollte man sich trotzdem nicht darauf: Das Handbuch sagt ausdrücklich, dass Elemente gleicher Priorität in keiner bestimmten Reihenfolge herauskommen, und bei 1000 Einträgen mit drei Stufen war die Eingangsreihenfolge im Test zerstört. Anders als sort(), das seit PHP 8.0 stabil sortiert, garantiert die Warteschlange nichts. Abhilfe schafft eine Priorität aus zwei Teilen. Arrays werden Element für Element verglichen, ein fallender Zähler entscheidet also bei Gleichstand:
<?php
$queue = new SplPriorityQueue();
$auftraege = ['A' => 2, 'B' => 1, 'C' => 2,
'D' => 1, 'E' => 2, 'F' => 1, 'G' => 2];
$n = 0;
foreach ($auftraege as $auftrag => $prio) {
$queue->insert($auftrag, [$prio, -$n++]);
}
while ($queue->valid()) {
echo $queue->extract();
}
/* ACEGBDF */
Ohne den Zähler kam dieselbe Liste als AGECDBF heraus. Soll die kleinste Priorität zuerst kommen, gibt es zwei Wege: die Priorität negativ übergeben oder eine Unterklasse schreiben, deren compare() mit $p2 <=> $p1 antwortet.
Extraktionsflags: Daten, Priorität oder beides
Standardmäßig gibt extract() nur die Daten zurück. Wer die Priorität ebenfalls braucht, etwa einen Zeitstempel, stellt das mit setExtractFlags() um. Gemessen mit zwei Einträgen, Mail mit Priorität 2 und Backup mit 9:
| Flag | Rückgabe von extract() |
EXTR_DATA (1, Standard) | "Backup" |
EXTR_PRIORITY (2) | 9 |
EXTR_BOTH (3) | Array mit den Schlüsseln data und priority |
<?php
$queue = new SplPriorityQueue();
$queue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$queue->insert('Mail', 2);
$queue->insert('Backup', 9);
print_r($queue->extract());
/* Array
(
[data] => Backup
[priority] => 9
) */
Das Flag gilt auch für Elemente, die schon in der Warteschlange liegen, und es wirkt genauso auf top() und foreach. setExtractFlags() gibt den gesetzten Wert zurück. Ein Wert ohne gültiges Bit, also 0 oder 4, endet in RuntimeException: Must specify at least one extract flag.
Fehlerfälle beim PHP Heap
Ein leerer Heap antwortet nicht mit null, sondern mit einer Exception. Das gilt für alle drei Klassen gleich:
<?php
$heap = new SplMinHeap();
try {
$heap->extract();
} catch (RuntimeException $e) {
echo $e->getMessage(), "\n";
}
/* Can't extract from an empty heap */
try {
$heap->top();
} catch (RuntimeException $e) {
echo $e->getMessage();
}
/* Can't peek at an empty heap */
Wer vorher isEmpty() prüft, braucht kein try. Wirft die eigene compare()-Methode eine Exception, etwa wegen eines fehlenden Feldes, gilt der Heap als beschädigt:
<?php
class Wackelig extends SplHeap
{
public bool $fehler = false;
protected function compare(
mixed $a,
mixed $b
): int {
if ($this->fehler) {
throw new RuntimeException('Feld fehlt');
}
return $b <=> $a;
}
}
$heap = new Wackelig();
$heap->insert(5);
$heap->insert(1);
$heap->fehler = true;
try {
$heap->insert(3);
} catch (RuntimeException $e) {
echo $e->getMessage(), "\n";
}
/* Feld fehlt */
var_dump($heap->isCorrupted(), count($heap));
/* bool(true)
int(3) */
$heap->fehler = false;
try {
$heap->extract();
} catch (RuntimeException $e) {
echo $e->getMessage();
}
/* Heap is corrupted, heap properties are no
longer ensured. */
count() zählt das abgebrochene Element mit. Von da an werfen insert(), extract(), top() und foreach dieselbe Meldung, nur count(), isEmpty() und isCorrupted() antworten noch. recoverFromCorruption() hebt die Sperre auf, repariert aber nichts. Bei 50 Zufallszahlen und einer Exception mitten in extract() kamen die übrigen 49 Werte danach in falscher Reihenfolge heraus. Ein beschädigter Heap wird deshalb neu aufgebaut.
Zwei weitere Fallen melden gar nichts. Ändert sich die Priorität eines Objekts, das schon im Heap liegt, ordnet er nicht neu: Job A mit Priorität 1 bekam nachträglich die 10 und kam trotzdem erst an zweiter Stelle. Und wer einen Heap in der Session ablegt, verliert ihn bis PHP 8.4 komplett. serialize() lieferte O:10:"SplMinHeap":0:{}, nach unserialize() war count() 0. Erst PHP 8.5 behält den Inhalt. Sicherer ist ein Array der Elemente, aus dem der PHP Heap beim Laden neu entsteht, etwa mit iterator_to_array(clone $heap, false).
Praxis: Top-N mit einem PHP Heap statt sort()
Zurück zu den zehn größten Bestellungen. Der Trick ist ein PHP Heap vom Typ SplMinHeap, der nie mehr als zehn Einträge hält. Oben liegt der kleinste der bisher besten zehn. Ist ein neuer Wert größer, fliegt der oberste raus:
<?php
function topN(iterable $werte, int $n): array
{
$heap = new SplMinHeap();
foreach ($werte as $wert) {
if ($heap->count() < $n) {
$heap->insert($wert);
} elseif ($wert > $heap->top()) {
$heap->extract();
$heap->insert($wert);
}
}
$liste = iterator_to_array($heap, false);
return array_reverse($liste);
}
function bestellwerte(): Generator
{
foreach ([120, 40, 990, 75, 310] as $wert) {
yield $wert;
}
}
echo implode(', ', topN(bestellwerte(), 3));
/* 990, 310, 120 */
Die Funktion nimmt Arrays und Generatoren. Kommen die Werte aus einer Datei oder Datenbank, liefert ein Generator mit yield sie Stück für Stück, und nichts muss vollständig im Speicher stehen. Gemessen mit einer Million Zufallszahlen, jeweils die zehn größten, Median aus drei Läufen:
| Weg | Windows | Linux |
Array: rsort() und array_slice() | 224,6 ms, +58 MiB | 207,3 ms, +56 MiB |
Array: topN() | 42,1 ms, kein Zusatzspeicher | 28,9 ms, kein Zusatzspeicher |
Generator: erst sammeln, dann rsort() | 264,6 ms, +58 MiB | 249,4 ms, +56 MiB |
Generator: topN() | 81,6 ms, kein Zusatzspeicher | 48,9 ms, kein Zusatzspeicher |
Für die zehn meistbesuchten Seiten aus 500.000 Zeilen brauchte usort() rund 2,2 Sekunden und gut 230 MiB zusätzlich, weil vorher alles in ein Array musste. Eine eigene SplHeap-Unterklasse mit derselben Begrenzung schaffte es in 94 ms unter Windows und 53 ms unter Linux, ohne messbaren Mehrbedarf. Soll dagegen die ganze Liste sortiert werden, verliert der Heap: Eine Million Werte einfügen und vollständig entnehmen dauerte zusammen rund 405 bis 475 ms, sort() auf demselben Array 163 bis 198 ms. Heapsort selbst zu bauen lohnt sich in PHP also nicht.
Praxis: Aufgaben nach Fälligkeit abarbeiten
Ein Cronjob soll anstehende Aufgaben in der Reihenfolge ihrer Fälligkeit erledigen, und Aufgaben mit derselben Uhrzeit in der Reihenfolge, in der sie angelegt wurden. Die SplPriorityQueue erledigt beides mit einer zweiteiligen Priorität. Weil die früheste Zeit oben liegen soll, wird der Zeitstempel negativ übergeben:
<?php
$aufgaben = [
['Rechnung', '2026-11-03 09:00'],
['Backup', '2026-11-02 23:00'],
['Newsletter', '2026-11-03 09:00'],
['Report', '2026-11-02 08:00'],
];
$queue = new SplPriorityQueue();
$n = 0;
foreach ($aufgaben as [$was, $wann]) {
$prio = [-strtotime($wann), -$n++];
$queue->insert($was, $prio);
}
while ($queue->valid()) {
echo $queue->extract(), "\n";
}
/* Report
Backup
Rechnung
Newsletter */
Rechnung und Newsletter sind gleichzeitig fällig, der Zähler hält die Reihenfolge fest.
Heap-Speicher ist etwas anderes
Oft ist mit „PHP Heap“ gar keine Datenstruktur gemeint, sondern der Bereich des Arbeitsspeichers, aus dem ein Programm zur Laufzeit Speicher anfordert. Verwaltet wird er vom Zend Memory Manager, freigegeben wird über Referenzzählung und den Garbage Collector, und memory_limit setzt die Obergrenze. Mit SplHeap verbindet ihn nur der Name, wobei auch ein Heap Platz in diesem Speicher belegt: Eine Million Ganzzahlen brauchten im SplMinHeap 16 MiB. Wie man den Verbrauch misst, erklärt das Tutorial zu memory_get_usage().
Fazit
Ein PHP Heap lohnt sich, wenn immer nur die Spitze gebraucht wird: die kleinsten oder größten Werte, der dringendste Auftrag, die zehn besten Einträge aus einem Datenstrom. SplMinHeap und SplMaxHeap decken Zahlen und Strings ab, eine eigene Unterklasse von SplHeap deckt Datensätze ab, und SplPriorityQueue passt, wenn Wert und Priorität getrennt sind. Für eine komplett sortierte Liste bleibt sort() schneller.
compare() zählt andersherum als usort(). foreach leert den Heap, ein clone hilft. Gleiche Prioritäten brauchen einen Zähler, wenn die Reihenfolge zählt. Nach einer Exception in compare() wird neu aufgebaut statt repariert. Und bis PHP 8.4 übersteht kein PHP Heap ein serialize().
