1package Heap;
2
3# heap is mainly here as documentation for the common heap interface.
4# It defaults to Heap::Fibonacci.
5
6use strict;
7use vars qw($VERSION);
8
9$VERSION = '0.80';
10
11sub new {
12    use Heap::Fibonacci;
13
14    return &Heap::Fibonacci::new;
15}
16
171;
18__END__
19
20=head1 NAME
21
22Heap - Perl extensions for keeping data partially sorted
23
24=head1 SYNOPSIS
25
26  use Heap;
27
28  my $heap = Heap->new;
29  my $elem;
30
31  use Heap::Elem::Num(NumElem);
32
33  foreach $i ( 1..100 ) {
34      $elem = NumElem( $i );
35      $heap->add( $elem );
36  }
37
38  while( defined( $elem = $heap->extract_top ) ) {
39      print "Smallest is ", $elem->val, "\n";
40  }
41
42=head1 DESCRIPTION
43
44The Heap collection of modules provide routines that manage
45a heap of elements.  A heap is a partially sorted structure
46that is always able to easily extract the smallest of the
47elements in the structure (or the largest if a reversed compare
48routine is provided).
49
50If the collection of elements is changing dynamically, the
51heap has less overhead than keeping the collection fully
52sorted.
53
54The elements must be objects as described in L<"Heap::Elem">
55and all elements inserted into one heap must be mutually
56compatible - either the same class exactly or else classes that
57differ only in ways unrelated to the B<Heap::Elem> interface.
58
59=head1 METHODS
60
61=over 4
62
63=item $heap = HeapClass::new(); $heap2 = $heap1->new();
64
65Returns a new heap object of the specified (sub-)class.
66This is often used as a subroutine instead of a method,
67of course.
68
69=item $heap->DESTROY
70
71Ensures that no internal circular data references remain.
72Some variants of Heap ignore this (they have no such references).
73Heap users normally need not worry about it, DESTROY is automatically
74invoked when the heap reference goes out of scope.
75
76=item $heap->add($elem)
77
78Add an element to the heap.
79
80=item $elem = $heap->top
81
82Return the top element on the heap.  It is B<not> removed from
83the heap but will remain at the top.  It will be the smallest
84element on the heap (unless a reversed cmp function is being
85used, in which case it will be the largest).  Returns I<undef>
86if the heap is empty.
87
88This method used to be called "minimum" instead of "top".  The
89old name is still supported but is deprecated.  (It was confusing
90to use the method "minimum" to get the maximum value on the heap
91when a reversed cmp function was used for ordering elements.)
92
93=item $elem = $heap->extract_top
94
95Delete the top element from the heap and return it.  Returns
96I<undef> if the heap was empty.
97
98This method used to be called "extract_minimum" instead of
99"extract_top".  The old name is still supported but is deprecated.
100(It was confusing to use the method "extract_minimum" to get the
101maximum value on the heap when a reversed cmp function was used
102for ordering elements.)
103
104=item $heap1->absorb($heap2)
105
106Merge all of the elements from I<$heap2> into I<$heap1>.
107This will leave I<$heap2> empty.
108
109=item $heap1->decrease_key($elem)
110
111The element will be moved closed to the top of the
112heap if it is now smaller than any higher parent elements.
113The user must have changed the value of I<$elem> before
114I<decrease_key> is called.  Only a decrease is permitted.
115(This is a decrease according to the I<cmp> function - if it
116is a reversed order comparison, then you are only permitted
117to increase the value of the element.  To be pedantic, you
118may only use I<decrease_key> if
119I<$elem->cmp($elem_original) <= 0> if I<$elem_original> were
120an elem with the value that I<$elem> had before it was
121I<decreased>.)
122
123=item $elem = $heap->delete($elem)
124
125The element is removed from the heap (whether it is at
126the top or not).
127
128=back
129
130=head1 AUTHOR
131
132John Macdonald, john@perlwolf.com
133
134=head1 COPYRIGHT
135
136Copyright 1998-2007, O'Reilly & Associates.
137
138This code is distributed under the same copyright terms as perl itself.
139
140=head1 SEE ALSO
141
142Heap::Elem(3), Heap::Binary(3), Heap::Binomial(3), Heap::Fibonacci(3).
143
144=cut
145