NAME
Array::Heap - treat perl arrays as heaps (priority queues)
SYNOPSIS
use Array::Heap;
DESCRIPTION
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 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.
FUNCTIONS
All of the following functions are being exported by default.
make_heap @heap (\@)
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).
make_heap_lex @heap (\@)
Just like "make_heap", but in string comparison order instead of
numerical comparison order.
make_heap_cmp { compare } @heap (&\@)
Just like "make_heap", but takes a custom comparison function.
push_heap @heap, $element, ... (\@@)
Adds the given element(s) to the heap.
push_heap_lex @heap, $element, ... (\@@)
Just like "push_heap", but in string comparison order instead of
numerical comparison order.
push_heap_cmp { compare } @heap, $element, ... (&\@@)
Just like "push_heap", but takes a custom comparison function.
pop_heap @heap (\@)
Removes the topmost (lowest) heap element and repairs the heap.
pop_heap_lex @heap (\@)
Just like "pop_heap", but in string comparison order instead of
numerical comparison order.
pop_heap_cmp { compare } @heap (&\@)
Just like "pop_heap", but takes a custom comparison function.
splice_heap @heap, $index (\@$)
Similar to "pop_heap", but removes and returns the element at index
$index.
splice_heap_lex @heap, $index (\@$)
Just like "splice_heap", but in string comparison order instead of
numerical comparison order.
splice_heap_cmp { compare } @heap, $index (&\@$)
Just like "splice_heap", but takes a custom comparison function.
adjust_heap @heap, $index (\@$)
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.
adjust_heap_lex @heap, $index (\@$)
Just like "adjust_heap", but in string comparison order instead of
numerical comparison order.
adjust_heap_cmp { compare } @heap, $index (&\@$)
Just like "adjust_heap", but takes a custom comparison function.
COMPARISON FUNCTIONS
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 cna 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.
BUGS
* Numerical comparison is always done using floatingpoint, which
usually has less precision than a 64 bit integer that perl might use
for integers internally, resulting in precision loss on the built-in
comparison.
* This module does not work with tied or magical arrays or array
elements, and, in fact, will even crash when you use those.
* This module can leak memory (or worse) when your comparison function
exits unexpectedly (e.g. "last") or throws an exception, so do not
do that.
AUTHOR
Marc Lehmann
http://home.schmorp.de/