-
Notifications
You must be signed in to change notification settings - Fork 5
SplMaxHeap
#SplHeap#
Heaps can be used to create ordered collections of arbitrary values.
The Spl provides two Heap implementations: SplMaxHeap
and SplMinHeap
. Both are subclasses of the abstract class SplHeap
. Like their name suggest, SplMaxHeap
will always yield the highest sorted item when extracting item froms the heap, while SplMinHeap
will always return the lowest sorted item. Heaps cannot be accessed by offset like Arrays but they can be traversed with foreach
. But since you can only access the highest or lowest sorted item, traversing a heap will extract this item (read: remove from the heap) to get to the next item.
When using SplMaxHeap::insert()
to add elements to the Heap, those will automatically be sorted by SplMaxHeap::compare()
. This is especially useful if you are adding items to the Heap in a non-consecutive manner, but need the elements sorted at any time. For large quantities of data SplMaxHeap
is much more efficient in terms of processing speed and memory consumption.
To use a Heap, you have to extend either SplMaxHeap
or SplMinHeap
and implement the abstract compare()
method.
##Examples##
<?php
class SortPeopleByAgeDescending extends SplMaxHeap
{
function compare($a, $b)
{
return $a->age - $b->age;
}
}
$jane = new StdClass;
$jane->age = 25;
$john = new StdClass;
$john->age = 30;
$june = new StdClass;
$june->age = 22;
$heap = new SortPeopleByAgeDescending();
$heap->insert($jane);
$heap->insert($john);
$heap->insert($june);
foreach($heap as $person) {
echo $person->age; // 30, 25, 22
}
echo $heap->count(); // 0
<?php
class SortNumbersDescending extends SplMaxHeap
{
function compare($a, $b)
{
return $a - $b;
}
}
$numbers = range(1,10);
shuffle($numbers); // randomize
$sorter = new SortNumbersDescending;
array_map(array($sorter, 'insert'), $numbers);
print_r(iterator_to_array($sorter)); // array is sorted from 10 to 1
Since SplMaxHeap::compare()
is just a regular method, you can also use it as a callback to use in other sorting functions, for instance usort
. However, when doing so, you have to check how the sorting function passes arguments to SplMaxHeap::compare()
. In the case of usort
, the order is reversed. This results in a reversed sorting order as well, e.g. the numbers will be sorted in ascending order.
<?php
$numbers = range(1,10);
shuffle($numbers); // randomize
$sorter = new SortNumbersDescending;
usort($numbers, array($sorter, 'compare'));
print_r($numbers); // array is sorted from 1 to 10