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.3 by root, Sun Jul 26 05:38:00 2009 UTC vs.
Revision 1.9 by root, Tue Jul 14 23:45:10 2015 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
… …
28=cut 28=cut
29 29
30package Array::Heap; 30package Array::Heap;
31 31
32BEGIN { 32BEGIN {
33 $VERSION = '2.0'; 33 $VERSION = 3.21;
34 34
35 require XSLoader; 35 require XSLoader;
36 XSLoader::load ("Array::Heap", $VERSION); 36 XSLoader::load ("Array::Heap", $VERSION);
37} 37}
38 38
39use base Exporter; 39use base Exporter;
40 40
41@EXPORT = qw( 41@EXPORT = qw(
42 make_heap make_heap_lex make_heap_cmp 42 make_heap make_heap_lex make_heap_cmp make_heap_idx
43 push_heap push_heap_lex push_heap_cmp 43 push_heap push_heap_lex push_heap_cmp push_heap_idx
44 pop_heap pop_heap_lex pop_heap_cmp 44 pop_heap pop_heap_lex pop_heap_cmp pop_heap_idx
45 splice_heap splice_heap_lex splice_heap_cmp 45 splice_heap splice_heap_lex splice_heap_cmp splice_heap_idx
46 adjust_heap adjust_heap_lex adjust_heap_cmp 46 adjust_heap adjust_heap_lex adjust_heap_cmp adjust_heap_idx
47); 47);
48 48
49=item make_heap @heap (\@) 49=item make_heap @heap (\@)
50 50
51Reorders 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
52value "on top" of the heap (corresponding to the first array element). 52value "on top" of the heap (corresponding to the first array element).
53 53
54=item make_heap_idx @heap (\@)
55
56Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS).
57
54=item make_heap_lex @heap (\@) 58=item make_heap_lex @heap (\@)
55 59
56Just 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
57comparison order. 61comparison order.
58 62
… …
62 66
63=item push_heap @heap, $element, ... (\@@) 67=item push_heap @heap, $element, ... (\@@)
64 68
65Adds the given element(s) to the heap. 69Adds the given element(s) to the heap.
66 70
71=item push_heap_idx @heap, $element, ... (\@@)
72
73Just like C<push_heap>, but updates the index (see INDEXED OPERATIONS).
74
67=item push_heap_lex @heap, $element, ... (\@@) 75=item push_heap_lex @heap, $element, ... (\@@)
68 76
69Just 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
70comparison order. 78comparison order.
71 79
… …
75 83
76=item pop_heap @heap (\@) 84=item pop_heap @heap (\@)
77 85
78Removes the topmost (lowest) heap element and repairs the heap. 86Removes the topmost (lowest) heap element and repairs the heap.
79 87
88=item pop_heap_idx @heap (\@)
89
90Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS).
91
80=item pop_heap_lex @heap (\@) 92=item pop_heap_lex @heap (\@)
81 93
82Just 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
83comparison order. 95comparison order.
84 96
… …
88 100
89=item splice_heap @heap, $index (\@$) 101=item splice_heap @heap, $index (\@$)
90 102
91Similar to C<pop_heap>, but removes and returns the element at index 103Similar to C<pop_heap>, but removes and returns the element at index
92C<$index>. 104C<$index>.
105
106=item splice_heap_idx @heap, $index (\@$)
107
108Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS).
93 109
94=item splice_heap_lex @heap, $index (\@$) 110=item splice_heap_lex @heap, $index (\@$)
95 111
96Just like C<splice_heap>, but in string comparison order instead of 112Just like C<splice_heap>, but in string comparison order instead of
97numerical comparison order. 113numerical comparison order.
… …
103=item adjust_heap @heap, $index (\@$) 119=item adjust_heap @heap, $index (\@$)
104 120
105Assuming you have only changed the element at index C<$index>, repair the 121Assuming you have only changed the element at index C<$index>, repair the
106heap again. Can be used to remove elements, replace elements, adjust the 122heap again. Can be used to remove elements, replace elements, adjust the
107priority of elements and more. 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).
108 128
109=item adjust_heap_lex @heap, $index (\@$) 129=item adjust_heap_lex @heap, $index (\@$)
110 130
111Just like C<adjust_heap>, but in string comparison order instead of 131Just like C<adjust_heap>, but in string comparison order instead of
112numerical comparison order. 132numerical comparison order.
… …
140will 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>.
141 161
142The 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>
143and 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
144greater than zero then $a is greater than $b, C<0> otherwise. This means 164greater than zero then $a is greater than $b, C<0> otherwise. This means
145that you cna use the same function as for sorting the array, but you could 165that you can use the same function as for sorting the array, but you could
146also use a simpler function that just does C<< $a > $b >>. 166also use a simpler function that just does C<< $a > $b >>.
147 167
148The first example above corresponds to this comparison "function": 168The first example above corresponds to this comparison "function":
149 169
150 { $a <=> $b } 170 { $a <=> $b }
… …
153 173
154 { $a->[0] <=> $b->[0] } 174 { $a->[0] <=> $b->[0] }
155 175
156Unlike 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
157use normal subroutines. 177use normal subroutines.
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.
158 189
159=head1 BUGS 190=head1 BUGS
160 191
161=over 4 192=over 4
162 193
… …
172function exits unexpectedly (e.g. C<last>) or throws an exception, so do 203function exits unexpectedly (e.g. C<last>) or throws an exception, so do
173not do that. 204not do that.
174 205
175=back 206=back
176 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
220
221 Marc Lehmann <schmorp@schmorp.de>
222 http://software.schmorp.de/pkg/Array-Heap
223
177=cut 224=cut
178 225
179=head1 AUTHOR
180
181 Marc Lehmann <schmorp@schmorp.de>
182 http://home.schmorp.de/
183
184=cut
185

Diff Legend

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