SPL Heaps
A heap is a container that always gives back the largest or smallest value first. SplMaxHeap and SplMinHeap keep that order as values are inserted.
A max heap extracts high to low
The numbers 10, 30 and 20 go into a SplMaxHeap here. extract takes them out one at a time, largest first.
<?php
$heap = new SplMaxHeap();
$heap->insert(10);
$heap->insert(30);
$heap->insert(20);
echo $heap->extract() . "\n";
echo $heap->extract() . "\n";
echo $heap->extract() . "\n";A min heap extracts low to high
The same three numbers go into a SplMinHeap here. extract takes them out one at a time, smallest first.
<?php
$heap = new SplMinHeap();
$heap->insert(10);
$heap->insert(30);
$heap->insert(20);
echo $heap->extract() . "\n";
echo $heap->extract() . "\n";
echo $heap->extract() . "\n";Words extract in word order
A SplMaxHeap compares words as text here. The word that sorts last in word order comes out first.
<?php
$heap = new SplMaxHeap();
$heap->insert("pear");
$heap->insert("apple");
$heap->insert("plum");
echo $heap->extract() . "\n";
echo $heap->extract() . "\n";
echo $heap->extract() . "\n";Example
<?php
$line = new SplPriorityQueue();
$line->insert("water the plants", 1);
$line->insert("fix the leak", 3);
$line->insert("paint the door", 2);
echo $line->extract() . "\n";
echo $line->extract() . "\n";
echo $line->extract() . "\n";Key points
- A heap orders its values as they are inserted.
- SplMaxHeap gives the largest value first.
- SplMinHeap gives the smallest value first.
- Use insert to add a value to a heap.
- Use extract to take the top value out of a heap.
- SplPriorityQueue pairs each value with a priority number and gives the highest priority first.
In this example, each task goes into the SplPriorityQueue with a priority number. The leak task carries 3, the door task carries 2 and the plants task carries 1. extract gives the tasks back from the highest priority to the lowest.
Note
Extracting from a heap removes the value, so the next extract moves to the next value in order.
Try it Yourself
Edit the code, then press Run.
Running is simulated
Exercise
A SplMaxHeap holds 5, 9 and 1. Which value does the first extract give?