PHP Reference ยท Standard PHP Library and Classes
The SplPriorityQueue and SplHeap classes
Reference for PHP SplPriorityQueue, SplMinHeap, SplMaxHeap and SplHeap: insert, extract, priorities, extract flags, custom ordering, ties and consuming iteration.
A heap keeps its elements partially ordered so that the "best" one is always available at the top, and inserting or removing takes logarithmic time. PHP provides SplMinHeap (smallest on top), SplMaxHeap (largest on top) and the abstract SplHeap for your own ordering.
SplPriorityQueue is a heap of values paired with separate priorities: you insert a value and say how urgent it is, and extract() always hands out the value with the highest priority. Use it for schedulers, "next best" searches and shortest-path algorithms.
<?php $queue = new SplPriorityQueue(); $queue->insert('low', 1); $queue->insert('high', 9); echo $queue->extract();
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.
Syntax
class SplPriorityQueue implements Iterator, Countable { public function insert(mixed $value, mixed $priority): true; public function extract(): mixed; } abstract class SplHeap implements Iterator, Countable { abstract protected function compare(mixed $value1, mixed $value2): int; public function insert(mixed $value): true; public function extract(): mixed; }
| Member | Description |
|---|---|
insert() |
Adds an element (for the priority queue, with a priority of any comparable type). |
extract() |
Removes and returns the top element. |
top() |
Returns the top element without removing it. |
count(), isEmpty(), valid() |
Size and emptiness. |
setExtractFlags($flags) |
Priority queue only: EXTR_DATA (value), EXTR_PRIORITY or EXTR_BOTH (array with data and priority). |
compare($a, $b) |
Return a positive number if $a should be nearer the top than $b. SplMinHeap and SplMaxHeap implement it; for a priority queue you may override it to change how priorities compare. |
Return value: extract() and top() return the element (or an array, with EXTR_BOTH).
Errors / Exceptions: extract() and top() on an empty structure throw RuntimeException. An exception thrown inside compare() can leave the heap corrupted; isCorrupted() and recoverFromCorruption() exist for that case.
Usage notes
- Highest priority first. Priorities are compared with the normal comparison rules, so arrays compare element by element; use
[priority, tiebreaker]for ordering within equal priorities. - Ties are not stable. Elements with equal priority come out in no guaranteed order. Add a decreasing counter as the second part of the priority, as shown above.
- Iterating consumes.
foreachover a heap or queue removes each element; copy it withclonefirst if you still need it. - No random access. There is no way to read the n-th element or remove an arbitrary one. If you need that, keep a sorted array.
- For a lowest-priority-first queue, negate numeric priorities or extend
SplPriorityQueueand overridecompare(). - Complexity.
insert()andextract()are O(log n);top()is O(1). - Plain sorting. To order a fixed list once,
sort()is simpler; use a heap when elements keep arriving and you only need the next best. - Return type
trueforinsert()is new in PHP 8.4; older versions returntruetoo, but are documented asbool.