-
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 1Since 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