1 | NAME |
1 | NAME |
2 | Array::Heap - treat perl arrays as heaps (priority queues) |
2 | Array::Heap - treat perl arrays as binary heaps/priority queues |
3 | |
3 | |
4 | SYNOPSIS |
4 | SYNOPSIS |
5 | use Array::Heap; |
5 | use Array::Heap; |
6 | |
6 | |
7 | DESCRIPTION |
7 | DESCRIPTION |
8 | There are a multitude of heap and heap-like modules on CPAN, you might |
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 |
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 |
10 | more or less fancy datastructures that might well be what you are |
11 | looking for. |
11 | looking for. |
12 | |
12 | |
13 | This module takes a different approach: It exports functions (i.e. not |
13 | This module takes a different approach: It exports functions (i.e. no |
14 | object orientation) that are loosely modeled after the C++ STL's heap |
14 | object orientation) that are loosely modeled after the C++ STL's binary |
15 | functions. They all take an array as argument, just like perl's built-in |
15 | heap functions. They all take an array as argument, just like perl's |
16 | functions "push", "pop" etc. |
16 | built-in functions "push", "pop" etc. |
17 | |
17 | |
18 | The implementation itself is in C for maximum speed (although I doubt it |
18 | The implementation itself is in C for maximum speed. |
19 | makes that much of a difference). |
|
|
20 | |
19 | |
21 | FUNCTIONS |
20 | FUNCTIONS |
22 | All of the following functions are being exported by default. |
21 | All of the following functions are being exported by default. |
23 | |
22 | |
24 | make_heap @heap (\@) |
23 | make_heap @heap (\@) |
25 | Reorders the elements in the array so they form a heap, with the |
24 | 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 |
25 | lowest value "on top" of the heap (corresponding to the first array |
27 | element). |
26 | element). |
|
|
27 | |
|
|
28 | make_heap_idx @heap (\@) |
|
|
29 | Just like "make_heap", but updates the index (see INDEXED |
|
|
30 | OPERATIONS). |
28 | |
31 | |
29 | make_heap_lex @heap (\@) |
32 | make_heap_lex @heap (\@) |
30 | Just like "make_heap", but in string comparison order instead of |
33 | Just like "make_heap", but in string comparison order instead of |
31 | numerical comparison order. |
34 | numerical comparison order. |
32 | |
35 | |
… | |
… | |
34 | Just like "make_heap", but takes a custom comparison function. |
37 | Just like "make_heap", but takes a custom comparison function. |
35 | |
38 | |
36 | push_heap @heap, $element, ... (\@@) |
39 | push_heap @heap, $element, ... (\@@) |
37 | Adds the given element(s) to the heap. |
40 | Adds the given element(s) to the heap. |
38 | |
41 | |
|
|
42 | push_heap_idx @heap, $element, ... (\@@) |
|
|
43 | Just like "push_heap", but updates the index (see INDEXED |
|
|
44 | OPERATIONS). |
|
|
45 | |
39 | push_heap_lex @heap, $element, ... (\@@) |
46 | push_heap_lex @heap, $element, ... (\@@) |
40 | Just like "push_heap", but in string comparison order instead of |
47 | Just like "push_heap", but in string comparison order instead of |
41 | numerical comparison order. |
48 | numerical comparison order. |
42 | |
49 | |
43 | push_heap_cmp { compare } @heap, $element, ... (&\@@) |
50 | push_heap_cmp { compare } @heap, $element, ... (&\@@) |
44 | Just like "push_heap", but takes a custom comparison function. |
51 | Just like "push_heap", but takes a custom comparison function. |
45 | |
52 | |
46 | pop_heap @heap (\@) |
53 | pop_heap @heap (\@) |
47 | Removes the topmost (lowest) heap element and repairs the heap. |
54 | Removes the topmost (lowest) heap element and repairs the heap. |
48 | |
55 | |
|
|
56 | pop_heap_idx @heap (\@) |
|
|
57 | Just like "pop_heap", but updates the index (see INDEXED |
|
|
58 | OPERATIONS). |
|
|
59 | |
49 | pop_heap_lex @heap (\@) |
60 | pop_heap_lex @heap (\@) |
50 | Just like "pop_heap", but in string comparison order instead of |
61 | Just like "pop_heap", but in string comparison order instead of |
51 | numerical comparison order. |
62 | numerical comparison order. |
52 | |
63 | |
53 | pop_heap_cmp { compare } @heap (&\@) |
64 | pop_heap_cmp { compare } @heap (&\@) |
54 | Just like "pop_heap", but takes a custom comparison function. |
65 | Just like "pop_heap", but takes a custom comparison function. |
|
|
66 | |
|
|
67 | splice_heap @heap, $index (\@$) |
|
|
68 | Similar to "pop_heap", but removes and returns the element at index |
|
|
69 | $index. |
|
|
70 | |
|
|
71 | splice_heap_idx @heap, $index (\@$) |
|
|
72 | Just like "splice_heap", but updates the index (see INDEXED |
|
|
73 | OPERATIONS). |
|
|
74 | |
|
|
75 | 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 | adjust_heap_idx @heap, $index (\@$) |
|
|
88 | Just like "adjust_heap", but updates the index (see INDEXED |
|
|
89 | OPERATIONS). |
|
|
90 | |
|
|
91 | 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. |
55 | |
97 | |
56 | COMPARISON FUNCTIONS |
98 | COMPARISON FUNCTIONS |
57 | All the functions come in two flavours: one that uses the built-in |
99 | All the functions come in two flavours: one that uses the built-in |
58 | comparison function and one that uses a custom comparison function. |
100 | comparison function and one that uses a custom comparison function. |
59 | |
101 | |
… | |
… | |
70 | |
112 | |
71 | will sort according to the first element of the arrays, i.e. "1,2,3". |
113 | will sort according to the first element of the arrays, i.e. "1,2,3". |
72 | |
114 | |
73 | The custom comparison functions work similar to how "sort" works: $a and |
115 | 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 |
116 | $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. |
117 | 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". |
76 | |
120 | |
77 | The first example above corresponds to this comparison "function": |
121 | The first example above corresponds to this comparison "function": |
78 | |
122 | |
79 | { $a <=> $b } |
123 | { $a <=> $b } |
80 | |
124 | |
… | |
… | |
83 | { $a->[0] <=> $b->[0] } |
127 | { $a->[0] <=> $b->[0] } |
84 | |
128 | |
85 | Unlike "sort", the default sort is numerical and it is not possible to |
129 | Unlike "sort", the default sort is numerical and it is not possible to |
86 | use normal subroutines. |
130 | use normal subroutines. |
87 | |
131 | |
|
|
132 | 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 | |
88 | BUGS |
142 | BUGS |
89 | This module works not work with tied or magical arrays or array |
143 | * Numerical comparison is always done using floatingpoint, which |
90 | elements. |
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. |
91 | |
147 | |
92 | AUTHOR |
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 | |
|
|
155 | AUTHOR AND CONTACT INFORMATION |
93 | Marc Lehmann <schmorp@schmorp.de> |
156 | Marc Lehmann <schmorp@schmorp.de> |
94 | http://home.schmorp.de/ |
157 | http://software.schmorp.de/pkg/Array-Heap |
95 | |
158 | |