1 |
root |
1.1 |
NAME |
2 |
root |
1.4 |
Array::Heap - treat perl arrays as binary heaps/priority queues |
3 |
root |
1.1 |
|
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 |
root |
1.2 |
This module takes a different approach: It exports functions (i.e. no |
14 |
root |
1.3 |
object orientation) that are loosely modeled after the C++ STL's binary |
15 |
|
|
heap functions. They all take an array as argument, just like perl's |
16 |
|
|
built-in functions "push", "pop" etc. |
17 |
root |
1.1 |
|
18 |
root |
1.2 |
The implementation itself is in C for maximum speed. |
19 |
root |
1.1 |
|
20 |
|
|
FUNCTIONS |
21 |
|
|
All of the following functions are being exported by default. |
22 |
|
|
|
23 |
|
|
make_heap @heap (\@) |
24 |
|
|
Reorders the elements in the array so they form a heap, with the |
25 |
|
|
lowest value "on top" of the heap (corresponding to the first array |
26 |
|
|
element). |
27 |
|
|
|
28 |
root |
1.3 |
make_heap_idx @heap (\@) |
29 |
|
|
Just like "make_heap", but updates the index (see INDEXED |
30 |
|
|
OPERATIONS). |
31 |
|
|
|
32 |
root |
1.1 |
make_heap_lex @heap (\@) |
33 |
|
|
Just like "make_heap", but in string comparison order instead of |
34 |
|
|
numerical comparison order. |
35 |
|
|
|
36 |
|
|
make_heap_cmp { compare } @heap (&\@) |
37 |
|
|
Just like "make_heap", but takes a custom comparison function. |
38 |
|
|
|
39 |
|
|
push_heap @heap, $element, ... (\@@) |
40 |
|
|
Adds the given element(s) to the heap. |
41 |
|
|
|
42 |
root |
1.3 |
push_heap_idx @heap, $element, ... (\@@) |
43 |
|
|
Just like "push_heap", but updates the index (see INDEXED |
44 |
|
|
OPERATIONS). |
45 |
|
|
|
46 |
root |
1.1 |
push_heap_lex @heap, $element, ... (\@@) |
47 |
|
|
Just like "push_heap", but in string comparison order instead of |
48 |
|
|
numerical comparison order. |
49 |
|
|
|
50 |
|
|
push_heap_cmp { compare } @heap, $element, ... (&\@@) |
51 |
|
|
Just like "push_heap", but takes a custom comparison function. |
52 |
|
|
|
53 |
|
|
pop_heap @heap (\@) |
54 |
|
|
Removes the topmost (lowest) heap element and repairs the heap. |
55 |
|
|
|
56 |
root |
1.3 |
pop_heap_idx @heap (\@) |
57 |
|
|
Just like "pop_heap", but updates the index (see INDEXED |
58 |
|
|
OPERATIONS). |
59 |
|
|
|
60 |
root |
1.1 |
pop_heap_lex @heap (\@) |
61 |
|
|
Just like "pop_heap", but in string comparison order instead of |
62 |
|
|
numerical comparison order. |
63 |
|
|
|
64 |
|
|
pop_heap_cmp { compare } @heap (&\@) |
65 |
|
|
Just like "pop_heap", but takes a custom comparison function. |
66 |
|
|
|
67 |
root |
1.2 |
splice_heap @heap, $index (\@$) |
68 |
|
|
Similar to "pop_heap", but removes and returns the element at index |
69 |
|
|
$index. |
70 |
|
|
|
71 |
root |
1.3 |
splice_heap_idx @heap, $index (\@$) |
72 |
|
|
Just like "splice_heap", but updates the index (see INDEXED |
73 |
|
|
OPERATIONS). |
74 |
|
|
|
75 |
root |
1.2 |
splice_heap_lex @heap, $index (\@$) |
76 |
|
|
Just like "splice_heap", but in string comparison order instead of |
77 |
|
|
numerical comparison order. |
78 |
|
|
|
79 |
|
|
splice_heap_cmp { compare } @heap, $index (&\@$) |
80 |
|
|
Just like "splice_heap", but takes a custom comparison function. |
81 |
|
|
|
82 |
|
|
adjust_heap @heap, $index (\@$) |
83 |
|
|
Assuming you have only changed the element at index $index, repair |
84 |
|
|
the heap again. Can be used to remove elements, replace elements, |
85 |
|
|
adjust the priority of elements and more. |
86 |
|
|
|
87 |
root |
1.3 |
adjust_heap_idx @heap, $index (\@$) |
88 |
|
|
Just like "adjust_heap", but updates the index (see INDEXED |
89 |
|
|
OPERATIONS). |
90 |
|
|
|
91 |
root |
1.2 |
adjust_heap_lex @heap, $index (\@$) |
92 |
|
|
Just like "adjust_heap", but in string comparison order instead of |
93 |
|
|
numerical comparison order. |
94 |
|
|
|
95 |
|
|
adjust_heap_cmp { compare } @heap, $index (&\@$) |
96 |
|
|
Just like "adjust_heap", but takes a custom comparison function. |
97 |
|
|
|
98 |
root |
1.1 |
COMPARISON FUNCTIONS |
99 |
|
|
All the functions come in two flavours: one that uses the built-in |
100 |
|
|
comparison function and one that uses a custom comparison function. |
101 |
|
|
|
102 |
|
|
The built-in comparison function can either compare scalar numerical |
103 |
|
|
values (string values for *_lex functions), or array refs. If the |
104 |
|
|
elements to compare are array refs, the first element of the array is |
105 |
|
|
used for comparison, i.e. |
106 |
|
|
|
107 |
|
|
1, 4, 6 |
108 |
|
|
|
109 |
|
|
will be sorted according to their numerical value, |
110 |
|
|
|
111 |
|
|
[1 => $obj1], [2 => $obj2], [3 => $obj3] |
112 |
|
|
|
113 |
|
|
will sort according to the first element of the arrays, i.e. "1,2,3". |
114 |
|
|
|
115 |
|
|
The custom comparison functions work similar to how "sort" works: $a and |
116 |
|
|
$b are set to the elements to be compared, and the result should be |
117 |
root |
1.2 |
greater than zero then $a is greater than $b, 0 otherwise. This means |
118 |
|
|
that you cna use the same function as for sorting the array, but you |
119 |
|
|
could also use a simpler function that just does "$a > $b". |
120 |
root |
1.1 |
|
121 |
|
|
The first example above corresponds to this comparison "function": |
122 |
|
|
|
123 |
|
|
{ $a <=> $b } |
124 |
|
|
|
125 |
|
|
And the second example corresponds to this: |
126 |
|
|
|
127 |
|
|
{ $a->[0] <=> $b->[0] } |
128 |
|
|
|
129 |
|
|
Unlike "sort", the default sort is numerical and it is not possible to |
130 |
|
|
use normal subroutines. |
131 |
|
|
|
132 |
root |
1.3 |
INDEXED OPERATIONS |
133 |
|
|
The functions whose names end in "_idx" also "update the index". That |
134 |
|
|
means that all elements must be array refs, with the first element being |
135 |
|
|
the heap value, and the second value being the array index: |
136 |
|
|
|
137 |
|
|
[$value, $index, ...] |
138 |
|
|
|
139 |
|
|
This allows you to quickly locate an element in the array when all you |
140 |
|
|
have is the array reference. |
141 |
|
|
|
142 |
root |
1.1 |
BUGS |
143 |
root |
1.2 |
* Numerical comparison is always done using floatingpoint, which |
144 |
|
|
usually has less precision than a 64 bit integer that perl might use |
145 |
|
|
for integers internally, resulting in precision loss on the built-in |
146 |
|
|
comparison. |
147 |
|
|
|
148 |
|
|
* This module does not work with tied or magical arrays or array |
149 |
|
|
elements, and, in fact, will even crash when you use those. |
150 |
|
|
|
151 |
|
|
* This module can leak memory (or worse) when your comparison function |
152 |
|
|
exits unexpectedly (e.g. "last") or throws an exception, so do not |
153 |
|
|
do that. |
154 |
root |
1.1 |
|
155 |
root |
1.3 |
AUTHOR AND CONTACT INFORMATION |
156 |
root |
1.1 |
Marc Lehmann <schmorp@schmorp.de> |
157 |
root |
1.3 |
http://software.schmorp.de/pkg/Array-Heap |
158 |
root |
1.1 |
|