| 1 |
NAME |
| 2 |
Array::Heap - treat perl arrays as heaps (priority queues) |
| 3 |
|
| 4 |
SYNOPSIS |
| 5 |
use Array::Heap; |
| 6 |
|
| 7 |
DESCRIPTION |
| 8 |
There are a multitude of heap and heap-like modules on CPAN, you might |
| 9 |
want to search for /Heap/ and /Priority/ to find many. They implement |
| 10 |
more or less fancy datastructures that might well be what you are |
| 11 |
looking for. |
| 12 |
|
| 13 |
This module takes a different approach: It exports functions (i.e. not |
| 14 |
object orientation) that are loosely modeled after the C++ STL's heap |
| 15 |
functions. They all take an array as argument, just like perl's built-in |
| 16 |
functions "push", "pop" etc. |
| 17 |
|
| 18 |
The implementation itself is in C for maximum speed (although I doubt it |
| 19 |
makes that much of a difference). |
| 20 |
|
| 21 |
FUNCTIONS |
| 22 |
All of the following functions are being exported by default. |
| 23 |
|
| 24 |
make_heap @heap (\@) |
| 25 |
Reorders the elements in the array so they form a heap, with the |
| 26 |
lowest value "on top" of the heap (corresponding to the first array |
| 27 |
element). |
| 28 |
|
| 29 |
make_heap_lex @heap (\@) |
| 30 |
Just like "make_heap", but in string comparison order instead of |
| 31 |
numerical comparison order. |
| 32 |
|
| 33 |
make_heap_cmp { compare } @heap (&\@) |
| 34 |
Just like "make_heap", but takes a custom comparison function. |
| 35 |
|
| 36 |
push_heap @heap, $element, ... (\@@) |
| 37 |
Adds the given element(s) to the heap. |
| 38 |
|
| 39 |
push_heap_lex @heap, $element, ... (\@@) |
| 40 |
Just like "push_heap", but in string comparison order instead of |
| 41 |
numerical comparison order. |
| 42 |
|
| 43 |
push_heap_cmp { compare } @heap, $element, ... (&\@@) |
| 44 |
Just like "push_heap", but takes a custom comparison function. |
| 45 |
|
| 46 |
pop_heap @heap (\@) |
| 47 |
Removes the topmost (lowest) heap element and repairs the heap. |
| 48 |
|
| 49 |
pop_heap_lex @heap (\@) |
| 50 |
Just like "pop_heap", but in string comparison order instead of |
| 51 |
numerical comparison order. |
| 52 |
|
| 53 |
pop_heap_cmp { compare } @heap (&\@) |
| 54 |
Just like "pop_heap", but takes a custom comparison function. |
| 55 |
|
| 56 |
COMPARISON FUNCTIONS |
| 57 |
All the functions come in two flavours: one that uses the built-in |
| 58 |
comparison function and one that uses a custom comparison function. |
| 59 |
|
| 60 |
The built-in comparison function can either compare scalar numerical |
| 61 |
values (string values for *_lex functions), or array refs. If the |
| 62 |
elements to compare are array refs, the first element of the array is |
| 63 |
used for comparison, i.e. |
| 64 |
|
| 65 |
1, 4, 6 |
| 66 |
|
| 67 |
will be sorted according to their numerical value, |
| 68 |
|
| 69 |
[1 => $obj1], [2 => $obj2], [3 => $obj3] |
| 70 |
|
| 71 |
will sort according to the first element of the arrays, i.e. "1,2,3". |
| 72 |
|
| 73 |
The custom comparison functions work similar to how "sort" works: $a and |
| 74 |
$b are set to the elements to be compared, and the result should be |
| 75 |
either -1 if $a is less than $b, or ">= 0" otherwise. |
| 76 |
|
| 77 |
The first example above corresponds to this comparison "function": |
| 78 |
|
| 79 |
{ $a <=> $b } |
| 80 |
|
| 81 |
And the second example corresponds to this: |
| 82 |
|
| 83 |
{ $a->[0] <=> $b->[0] } |
| 84 |
|
| 85 |
Unlike "sort", the default sort is numerical and it is not possible to |
| 86 |
use normal subroutines. |
| 87 |
|
| 88 |
BUGS |
| 89 |
This module works not work with tied or magical arrays or array |
| 90 |
elements. |
| 91 |
|
| 92 |
AUTHOR |
| 93 |
Marc Lehmann <schmorp@schmorp.de> |
| 94 |
http://home.schmorp.de/ |
| 95 |
|
