ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Array-Heap/Heap.pm
(Generate patch)

Comparing Array-Heap/Heap.pm (file contents):
Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs.
Revision 1.10 by root, Wed Dec 7 12:06:35 2016 UTC

1=head1 NAME 1=head1 NAME
2 2
3Array::Heap - treat perl arrays as heaps (priority queues) 3Array::Heap - treat perl arrays as binary heaps/priority queues
4 4
5=head1 SYNOPSIS 5=head1 SYNOPSIS
6 6
7 use Array::Heap; 7 use Array::Heap;
8 8
… …
10 10
11There are a multitude of heap and heap-like modules on CPAN, you might 11There are a multitude of heap and heap-like modules on CPAN, you might
12want to search for /Heap/ and /Priority/ to find many. They implement more 12want to search for /Heap/ and /Priority/ to find many. They implement more
13or less fancy datastructures that might well be what you are looking for. 13or less fancy datastructures that might well be what you are looking for.
14 14
15This module takes a different approach: It exports functions (i.e. not 15This module takes a different approach: It exports functions (i.e. no
16object orientation) that are loosely modeled after the C++ STL's heap 16object orientation) that are loosely modeled after the C++ STL's binary
17functions. They all take an array as argument, just like perl's built-in 17heap functions. They all take an array as argument, just like perl's
18functions C<push>, C<pop> etc. 18built-in functions C<push>, C<pop> etc.
19 19
20The implementation itself is in C for maximum speed (although I doubt it 20The implementation itself is in C for maximum speed.
21makes that much of a difference).
22 21
23=head1 FUNCTIONS 22=head1 FUNCTIONS
24 23
25All of the following functions are being exported by default. 24All of the following functions are being exported by default.
26 25
… …
29=cut 28=cut
30 29
31package Array::Heap; 30package Array::Heap;
32 31
33BEGIN { 32BEGIN {
34 $VERSION = "1.2"; 33 $VERSION = 3.22;
35 34
36 require XSLoader; 35 require XSLoader;
37 XSLoader::load Array::Heap, $VERSION; 36 XSLoader::load ("Array::Heap", $VERSION);
38} 37}
39 38
40use base Exporter; 39use base Exporter;
41 40
42@EXPORT = qw(make_heap make_heap_lex make_heap_cmp push_heap push_heap_lex push_heap_cmp pop_heap pop_heap_lex pop_heap_cmp); 41@EXPORT = qw(
42 make_heap make_heap_lex make_heap_cmp make_heap_idx
43 push_heap push_heap_lex push_heap_cmp push_heap_idx
44 pop_heap pop_heap_lex pop_heap_cmp pop_heap_idx
45 splice_heap splice_heap_lex splice_heap_cmp splice_heap_idx
46 adjust_heap adjust_heap_lex adjust_heap_cmp adjust_heap_idx
47);
43 48
44=item make_heap @heap (\@) 49=item make_heap @heap (\@)
45 50
46Reorders the elements in the array so they form a heap, with the lowest 51Reorders the elements in the array so they form a heap, with the lowest
47value "on top" of the heap (corresponding to the first array element). 52value "on top" of the heap (corresponding to the first array element).
48 53
54=item make_heap_idx @heap (\@)
55
56Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS).
57
49=item make_heap_lex @heap (\@) 58=item make_heap_lex @heap (\@)
50 59
51Just like C<make_heap>, but in string comparison order instead of numerical 60Just like C<make_heap>, but in string comparison order instead of numerical
52comparison order. 61comparison order.
53 62
… …
57 66
58=item push_heap @heap, $element, ... (\@@) 67=item push_heap @heap, $element, ... (\@@)
59 68
60Adds the given element(s) to the heap. 69Adds the given element(s) to the heap.
61 70
71=item push_heap_idx @heap, $element, ... (\@@)
72
73Just like C<push_heap>, but updates the index (see INDEXED OPERATIONS).
74
62=item push_heap_lex @heap, $element, ... (\@@) 75=item push_heap_lex @heap, $element, ... (\@@)
63 76
64Just like C<push_heap>, but in string comparison order instead of numerical 77Just like C<push_heap>, but in string comparison order instead of numerical
65comparison order. 78comparison order.
66 79
… …
70 83
71=item pop_heap @heap (\@) 84=item pop_heap @heap (\@)
72 85
73Removes the topmost (lowest) heap element and repairs the heap. 86Removes the topmost (lowest) heap element and repairs the heap.
74 87
88=item pop_heap_idx @heap (\@)
89
90Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS).
91
75=item pop_heap_lex @heap (\@) 92=item pop_heap_lex @heap (\@)
76 93
77Just like C<pop_heap>, but in string comparison order instead of numerical 94Just like C<pop_heap>, but in string comparison order instead of numerical
78comparison order. 95comparison order.
79 96
80=item pop_heap_cmp { compare } @heap (&\@) 97=item pop_heap_cmp { compare } @heap (&\@)
81 98
82Just like C<pop_heap>, but takes a custom comparison function. 99Just like C<pop_heap>, but takes a custom comparison function.
100
101=item splice_heap @heap, $index (\@$)
102
103Similar to C<pop_heap>, but removes and returns the element at index
104C<$index>.
105
106=item splice_heap_idx @heap, $index (\@$)
107
108Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS).
109
110=item splice_heap_lex @heap, $index (\@$)
111
112Just like C<splice_heap>, but in string comparison order instead of
113numerical comparison order.
114
115=item splice_heap_cmp { compare } @heap, $index (&\@$)
116
117Just like C<splice_heap>, but takes a custom comparison function.
118
119=item adjust_heap @heap, $index (\@$)
120
121Assuming you have only changed the element at index C<$index>, repair the
122heap again. Can be used to remove elements, replace elements, adjust the
123priority of elements and more.
124
125=item adjust_heap_idx @heap, $index (\@$)
126
127Just like C<adjust_heap>, but updates the index (see INDEXED OPERATIONS).
128
129=item adjust_heap_lex @heap, $index (\@$)
130
131Just like C<adjust_heap>, but in string comparison order instead of
132numerical comparison order.
133
134=item adjust_heap_cmp { compare } @heap, $index (&\@$)
135
136Just like C<adjust_heap>, but takes a custom comparison function.
83 137
84=cut 138=cut
85 139
861; 1401;
87 141
… …
105 159
106will sort according to the first element of the arrays, i.e. C<1,2,3>. 160will sort according to the first element of the arrays, i.e. C<1,2,3>.
107 161
108The custom comparison functions work similar to how C<sort> works: C<$a> 162The custom comparison functions work similar to how C<sort> works: C<$a>
109and C<$b> are set to the elements to be compared, and the result should be 163and C<$b> are set to the elements to be compared, and the result should be
110either C<-1> if C<$a> is less than C<$b>, or C<< >= 0 >> otherwise. 164greater than zero then $a is greater than $b, C<0> otherwise. This means
165that you can use the same function as for sorting the array, but you could
166also use a simpler function that just does C<< $a > $b >>.
111 167
112The first example above corresponds to this comparison "function": 168The first example above corresponds to this comparison "function":
113 169
114 { $a <=> $b } 170 { $a <=> $b }
115 171
… …
118 { $a->[0] <=> $b->[0] } 174 { $a->[0] <=> $b->[0] }
119 175
120Unlike C<sort>, the default sort is numerical and it is not possible to 176Unlike C<sort>, the default sort is numerical and it is not possible to
121use normal subroutines. 177use normal subroutines.
122 178
179=head2 INDEXED OPERATIONS
180
181The functions whose names end in C<_idx> also "update the index". That
182means that all elements must be array refs, with the first element being
183the heap value, and the second value being the array index:
184
185 [$value, $index, ...]
186
187This allows you to quickly locate an element in the array when all you
188have is the array reference.
189
123=head1 BUGS 190=head1 BUGS
124 191
125This module works not work with tied or magical arrays or array elements. 192=over 4
126 193
127=head1 AUTHOR 194=item * Numerical comparison is always done using floatingpoint, which
195usually has less precision than a 64 bit integer that perl might use
196for integers internally, resulting in precision loss on the built-in
197comparison.
198
199=item * This module does not work with tied or magical arrays or array
200elements, and, in fact, will even crash when you use those.
201
202=item * This module can leak memory (or worse) when your comparison
203function exits unexpectedly (e.g. C<last>) or throws an exception, so do
204not do that.
205
206=back
207
208=head1 SEE ALSO
209
210This module has a rather low-level interface. If it seems daunting, you
211should have a look at L<Array::Heap::ModifiablePriorityQueue>, which is
212based on this module but provides more and higher-level operations with an
213object-oriented API which makes it harder to make mistakes.
214
215A slightly less flexible (only numeric weights), but also
216slightly faster variant of that module can be found as
217L<Array::Heap::PriorityQueue::Numeric> on CPAN.
218
219=head1 AUTHOR AND CONTACT INFORMATION
128 220
129 Marc Lehmann <schmorp@schmorp.de> 221 Marc Lehmann <schmorp@schmorp.de>
130 http://home.schmorp.de/ 222 http://software.schmorp.de/pkg/Array-Heap
131 223
132=cut 224=cut
133 225

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines