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.4 by root, Fri Apr 19 20:00:54 2013 UTC

… …
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.
… …
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.
158 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
159=head1 BUGS 190=head1 BUGS
160 191
161=over 4 192=over 4
162 193
163=item * Numerical comparison is always done using floatingpoint, which 194=item * Numerical comparison is always done using floatingpoint, which
… …
174 205
175=back 206=back
176 207
177=cut 208=cut
178 209
179=head1 AUTHOR 210=head1 AUTHOR AND CONTACT INFORMATION
180 211
181 Marc Lehmann <schmorp@schmorp.de> 212 Marc Lehmann <schmorp@schmorp.de>
182 http://home.schmorp.de/ 213 http://software.schmorp.de/pkg/Array-Heap
183 214
184=cut 215=cut
185 216

Diff Legend

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