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

Comparing Array-Heap/README (file contents):
Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs.
Revision 1.6 by root, Tue Jul 14 23:45:10 2015 UTC

1NAME 1NAME
2 Array::Heap - treat perl arrays as heaps (priority queues) 2 Array::Heap - treat perl arrays as binary heaps/priority queues
3 3
4SYNOPSIS 4SYNOPSIS
5 use Array::Heap; 5 use Array::Heap;
6 6
7DESCRIPTION 7DESCRIPTION
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
21FUNCTIONS 20FUNCTIONS
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 can 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
88BUGS 142BUGS
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
92AUTHOR 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
155SEE ALSO
156 This module has a rather low-level interface. If it seems daunting, you
157 should have a look at Array::Heap::ModifiablePriorityQueue, which is
158 based on this module but provides more and higher-level operations with
159 an object-oriented API which makes it harder to make mistakes.
160
161 A slightly less flexible (only numeric weights), but also slightly
162 faster variant of that module can be found as
163 Array::Heap::PriorityQueue::Numeric on CPAN.
164
165AUTHOR AND CONTACT INFORMATION
93 Marc Lehmann <schmorp@schmorp.de> 166 Marc Lehmann <schmorp@schmorp.de>
94 http://home.schmorp.de/ 167 http://software.schmorp.de/pkg/Array-Heap
95 168

Diff Legend

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