Array-Heap/Heap.pm

=head1 NAME

Array::Heap - treat perl arrays as 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. not
object orientation) that are loosely modeled after the C++ STL's 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 (although I doubt it
makes that much of a difference).

=head1 FUNCTIONS

All of the following functions are being exported by default.

=over 4

=cut

package Array::Heap;

BEGIN {
   $VERSION = "1.2";

   require XSLoader;
   XSLoader::load Array::Heap, $VERSION;
}

use base Exporter;

@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);

=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_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_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_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.

=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
either C<-1> if C<$a> is less than C<$b>, or C<< >= 0 >> otherwise.

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.

=head1 BUGS

This module works not work with tied or magical arrays or array elements.

=head1 AUTHOR

 Marc Lehmann <schmorp@schmorp.de>
 http://home.schmorp.de/

=cut

Revision:	1.1
Committed:	Wed Jul 1 08:31:34 2009 UTC (14 years, 10 months ago) by root
Branch:	MAIN
CVS Tags:	rel-1_2
Log Message:	1.2
#	User	Rev	Content
1	root	1.1	=head1 NAME
2
3			Array::Heap - treat perl arrays as 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. not
16			object orientation) that are loosely modeled after the C++ STL's heap
17			functions. They all take an array as argument, just like perl's built-in
18			functions C<push>, C<pop> etc.
19
20			The implementation itself is in C for maximum speed (although I doubt it
21			makes that much of a difference).
22
23			=head1 FUNCTIONS
24
25			All of the following functions are being exported by default.
26
27			=over 4
28
29			=cut
30
31			package Array::Heap;
32
33			BEGIN {
34			$VERSION = "1.2";
35
36			require XSLoader;
37			XSLoader::load Array::Heap, $VERSION;
38			}
39
40			use base Exporter;
41
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);
43
44			=item make_heap @heap (\@)
45
46			Reorders the elements in the array so they form a heap, with the lowest
47			value "on top" of the heap (corresponding to the first array element).
48
49			=item make_heap_lex @heap (\@)
50
51			Just like C<make_heap>, but in string comparison order instead of numerical
52			comparison order.
53
54			=item make_heap_cmp { compare } @heap (&\@)
55
56			Just like C<make_heap>, but takes a custom comparison function.
57
58			=item push_heap @heap, $element, ... (\@@)
59
60			Adds the given element(s) to the heap.
61
62			=item push_heap_lex @heap, $element, ... (\@@)
63
64			Just like C<push_heap>, but in string comparison order instead of numerical
65			comparison order.
66
67			=item push_heap_cmp { compare } @heap, $element, ... (&\@@)
68
69			Just like C<push_heap>, but takes a custom comparison function.
70
71			=item pop_heap @heap (\@)
72
73			Removes the topmost (lowest) heap element and repairs the heap.
74
75			=item pop_heap_lex @heap (\@)
76
77			Just like C<pop_heap>, but in string comparison order instead of numerical
78			comparison order.
79
80			=item pop_heap_cmp { compare } @heap (&\@)
81
82			Just like C<pop_heap>, but takes a custom comparison function.
83
84			=cut
85
86			1;
87
88			=back
89
90			=head2 COMPARISON FUNCTIONS
91
92			All the functions come in two flavours: one that uses the built-in
93			comparison function and one that uses a custom comparison function.
94
95			The built-in comparison function can either compare scalar numerical
96			values (string values for *_lex functions), or array refs. If the elements
97			to compare are array refs, the first element of the array is used for
98			comparison, i.e.
99
100			1, 4, 6
101
102			will be sorted according to their numerical value,
103
104			[1 => $obj1], [2 => $obj2], [3 => $obj3]
105
106			will sort according to the first element of the arrays, i.e. C<1,2,3>.
107
108			The custom comparison functions work similar to how C<sort> works: C<$a>
109			and C<$b> are set to the elements to be compared, and the result should be
110			either C<-1> if C<$a> is less than C<$b>, or C<< >= 0 >> otherwise.
111
112			The first example above corresponds to this comparison "function":
113
114			{ $a <=> $b }
115
116			And the second example corresponds to this:
117
118			{ $a->[0] <=> $b->[0] }
119
120			Unlike C<sort>, the default sort is numerical and it is not possible to
121			use normal subroutines.
122
123			=head1 BUGS
124
125			This module works not work with tied or magical arrays or array elements.
126
127			=head1 AUTHOR
128
129			Marc Lehmann <schmorp@schmorp.de>
130			http://home.schmorp.de/
131
132			=cut
133