Array-Heap/Heap.pm

=head1 NAME

Array::Heap - treat perl arrays as binary heaps/priority queues

=head1 SYNOPSIS

 use Array::Heap;

=head1 DESCRIPTION

There are a multitude of heap and heap-like modules on CPAN, you might
want to search for /Heap/ and /Priority/ to find many. They implement more
or less fancy datastructures that might well be what you are looking for.

This module takes a different approach: It exports functions (i.e. no
object orientation) that are loosely modeled after the C++ STL's binary
heap functions. They all take an array as argument, just like perl's
built-in functions C<push>, C<pop> etc.

The implementation itself is in C for maximum speed.

=head1 FUNCTIONS

All of the following functions are being exported by default.

=over 4

=cut

package Array::Heap;

BEGIN {
   $VERSION = 3.22;

   require XSLoader;
   XSLoader::load ("Array::Heap", $VERSION);
}

use base Exporter;

@EXPORT = qw(
   make_heap   make_heap_lex   make_heap_cmp   make_heap_idx
   push_heap   push_heap_lex   push_heap_cmp   push_heap_idx
   pop_heap    pop_heap_lex    pop_heap_cmp    pop_heap_idx
   splice_heap splice_heap_lex splice_heap_cmp splice_heap_idx
   adjust_heap adjust_heap_lex adjust_heap_cmp adjust_heap_idx
);

=item make_heap @heap                                   (\@)

Reorders the elements in the array so they form a heap, with the lowest
value "on top" of the heap (corresponding to the first array element).

=item make_heap_idx @heap                               (\@)

Just like C<make_heap>, but updates the index (see INDEXED OPERATIONS).

=item make_heap_lex @heap                               (\@)

Just like C<make_heap>, but in string comparison order instead of numerical
comparison order.

=item make_heap_cmp { compare } @heap                   (&\@)

Just like C<make_heap>, but takes a custom comparison function.

=item push_heap @heap, $element, ...                    (\@@)

Adds the given element(s) to the heap.

=item push_heap_idx @heap, $element, ...                (\@@)

Just like C<push_heap>,  but updates the index (see INDEXED OPERATIONS).

=item push_heap_lex @heap, $element, ...                (\@@)

Just like C<push_heap>, but in string comparison order instead of numerical
comparison order.

=item push_heap_cmp { compare } @heap, $element, ...    (&\@@)

Just like C<push_heap>, but takes a custom comparison function.

=item pop_heap @heap                                    (\@)

Removes the topmost (lowest) heap element and repairs the heap.

=item pop_heap_idx @heap                                (\@)

Just like C<pop_heap>, but updates the index (see INDEXED OPERATIONS).

=item pop_heap_lex @heap                                (\@)

Just like C<pop_heap>, but in string comparison order instead of numerical
comparison order.

=item pop_heap_cmp { compare } @heap                    (&\@)

Just like C<pop_heap>, but takes a custom comparison function.

=item splice_heap @heap, $index                         (\@$)

Similar to C<pop_heap>, but removes and returns the element at index
C<$index>.

=item splice_heap_idx @heap, $index                     (\@$)

Just like C<splice_heap>, but updates the index (see INDEXED OPERATIONS).

=item splice_heap_lex @heap, $index                     (\@$)

Just like C<splice_heap>, but in string comparison order instead of
numerical comparison order.

=item splice_heap_cmp { compare } @heap, $index         (&\@$)

Just like C<splice_heap>, but takes a custom comparison function.

=item adjust_heap @heap, $index                         (\@$)

Assuming you have only changed the element at index C<$index>, repair the
heap again. Can be used to remove elements, replace elements, adjust the
priority of elements and more.

=item adjust_heap_idx @heap, $index                     (\@$)

Just like C<adjust_heap>, but updates the index (see INDEXED OPERATIONS).

=item adjust_heap_lex @heap, $index                     (\@$)

Just like C<adjust_heap>, but in string comparison order instead of
numerical comparison order.

=item adjust_heap_cmp { compare } @heap, $index         (&\@$)

Just like C<adjust_heap>, but takes a custom comparison function.

=cut

1;

=back

=head2 COMPARISON FUNCTIONS

All the functions come in two flavours: one that uses the built-in
comparison function and one that uses a custom comparison function.

The built-in comparison function can either compare scalar numerical
values (string values for *_lex functions), or array refs. If the elements
to compare are array refs, the first element of the array is used for
comparison, i.e.

  1, 4, 6

will be sorted according to their numerical value,

  [1 => $obj1], [2 => $obj2], [3 => $obj3]

will sort according to the first element of the arrays, i.e. C<1,2,3>.

The custom comparison functions work similar to how C<sort> works: C<$a>
and C<$b> are set to the elements to be compared, and the result should be
greater than zero then $a is greater than $b, C<0> otherwise. This means
that you can use the same function as for sorting the array, but you could
also use a simpler function that just does C<< $a > $b >>.

The first example above corresponds to this comparison "function":

  { $a <=> $b }

And the second example corresponds to this:

  { $a->[0] <=> $b->[0] }

Unlike C<sort>, the default sort is numerical and it is not possible to
use normal subroutines.

=head2 INDEXED OPERATIONS

The functions whose names end in C<_idx> also "update the index". That
means that all elements must be array refs, with the first element being
the heap value, and the second value being the array index:

  [$value, $index, ...]

This allows you to quickly locate an element in the array when all you
have is the array reference.

=head1 BUGS

=over 4

=item * Numerical comparison is always done using floatingpoint, which
usually has less precision than a 64 bit integer that perl might use
for integers internally, resulting in precision loss on the built-in
comparison.

=item * This module does not work with tied or magical arrays or array
elements, and, in fact, will even crash when you use those.

=item * This module can leak memory (or worse) when your comparison
function exits unexpectedly (e.g. C<last>) or throws an exception, so do
not do that.

=back

=head1 SEE ALSO

This module has a rather low-level interface. If it seems daunting, you
should have a look at L<Array::Heap::ModifiablePriorityQueue>, which is
based on this module but provides more and higher-level operations with an
object-oriented API which makes it harder to make mistakes.

A slightly less flexible (only numeric weights), but also
slightly faster variant of that module can be found as
L<Array::Heap::PriorityQueue::Numeric> on CPAN.

=head1 AUTHOR AND CONTACT INFORMATION

 Marc Lehmann <schmorp@schmorp.de>
 http://software.schmorp.de/pkg/Array-Heap

=cut

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