Skip to content
Tutorials Center
My learning

Topics

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
<?php
$queue = new SplPriorityQueue();
$queue->insert('low', 1);
$queue->insert('high', 9);
echo $queue->extract();

Try it

PHP SplPriorityQueue and extract flags

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.

PHP Heaps, custom ordering and stable ties

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

PHP
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. foreach over a heap or queue removes each element; copy it with clone first 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 SplPriorityQueue and override compare().
  • Complexity. insert() and extract() 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 true for insert() is new in PHP 8.4; older versions return true too, but are documented as bool.