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