Array::Heap - treat perl arrays as binary heaps/priority queues
use Array::Heap;
There are a multitude of heap and heap-like modules on CPAN, you might want to search for /Heap/ and /Priority/ to find many. They implement more or less fancy datastructures that might well be what you are looking for.
This module takes a different approach: It exports functions (i.e. no object orientation) that are loosely modeled after the C++ STL's binary heap functions. They all take an array as argument, just like perl's built-in functions push
, pop
etc.
The implementation itself is in C for maximum speed.
All of the following functions are being exported by default.
Reorders the elements in the array so they form a heap, with the lowest value "on top" of the heap (corresponding to the first array element).
Just like make_heap
, but updates the index (see INDEXED OPERATIONS).
Just like make_heap
, but in string comparison order instead of numerical comparison order.
Just like make_heap
, but takes a custom comparison function.
Adds the given element(s) to the heap.
Just like push_heap
, but updates the index (see INDEXED OPERATIONS).
Just like push_heap
, but in string comparison order instead of numerical comparison order.
Just like push_heap
, but takes a custom comparison function.
Removes the topmost (lowest) heap element and repairs the heap.
Just like pop_heap
, but updates the index (see INDEXED OPERATIONS).
Just like pop_heap
, but in string comparison order instead of numerical comparison order.
Just like pop_heap
, but takes a custom comparison function.
Similar to pop_heap
, but removes and returns the element at index $index
.
Just like splice_heap
, but updates the index (see INDEXED OPERATIONS).
Just like splice_heap
, but in string comparison order instead of numerical comparison order.
Just like splice_heap
, but takes a custom comparison function.
Assuming you have only changed the element at index $index
, repair the heap again. Can be used to remove elements, replace elements, adjust the priority of elements and more.
Just like adjust_heap
, but updates the index (see INDEXED OPERATIONS).
Just like adjust_heap
, but in string comparison order instead of numerical comparison order.
Just like adjust_heap
, but takes a custom comparison function.
All the functions come in two flavours: one that uses the built-in comparison function and one that uses a custom comparison function.
The built-in comparison function can either compare scalar numerical values (string values for *_lex functions), or array refs. If the elements to compare are array refs, the first element of the array is used for comparison, i.e.
1, 4, 6
will be sorted according to their numerical value,
[1 => $obj1], [2 => $obj2], [3 => $obj3]
will sort according to the first element of the arrays, i.e. 1,2,3
.
The custom comparison functions work similar to how sort
works: $a
and $b
are set to the elements to be compared, and the result should be greater than zero then $a is greater than $b, 0
otherwise. This means that you can use the same function as for sorting the array, but you could also use a simpler function that just does $a > $b
.
The first example above corresponds to this comparison "function":
{ $a <=> $b }
And the second example corresponds to this:
{ $a->[0] <=> $b->[0] }
Unlike sort
, the default sort is numerical and it is not possible to use normal subroutines.
The functions whose names end in _idx
also "update the index". That means that all elements must be array refs, with the first element being the heap value, and the second value being the array index:
[$value, $index, ...]
This allows you to quickly locate an element in the array when all you have is the array reference.
last
) or throws an exception, so do not do that.This module has a rather low-level interface. If it seems daunting, you should have a look at Array::Heap::ModifiablePriorityQueue, which is based on this module but provides more and higher-level operations with an object-oriented API which makes it harder to make mistakes.
A slightly less flexible (only numeric weights), but also slightly faster variant of that module can be found as Array::Heap::PriorityQueue::Numeric on CPAN.
Marc Lehmann <schmorp@schmorp.de> http://software.schmorp.de/pkg/Array-Heap