NAME¶
Heap - Perl extensions for keeping data partially sorted
SYNOPSIS¶
use Heap;
my $heap = Heap->new;
my $elem;
use Heap::Elem::Num(NumElem);
foreach $i ( 1..100 ) {
$elem = NumElem( $i );
$heap->add( $elem );
}
while( defined( $elem = $heap->extract_top ) ) {
print "Smallest is ", $elem->val, "\n";
}
DESCRIPTION¶
The Heap collection of modules provide routines that manage a heap of elements.
A heap is a partially sorted structure that is always able to easily extract
the smallest of the elements in the structure (or the largest if a reversed
compare routine is provided).
If the collection of elements is changing dynamically, the heap has less
overhead than keeping the collection fully sorted.
The elements must be objects as described in "Heap::Elem" and all
elements inserted into one heap must be mutually compatible - either the same
class exactly or else classes that differ only in ways unrelated to the
Heap::Elem interface.
METHODS¶
- $heap = HeapClass::new(); $heap2 = $heap1->new();
- Returns a new heap object of the specified (sub-)class. This is often used
as a subroutine instead of a method, of course.
- $heap->DESTROY
- Ensures that no internal circular data references remain. Some variants of
Heap ignore this (they have no such references). Heap users normally need
not worry about it, DESTROY is automatically invoked when the heap
reference goes out of scope.
- $heap->add($elem)
- Add an element to the heap.
- $elem = $heap->top
- Return the top element on the heap. It is not removed from the heap
but will remain at the top. It will be the smallest element on the heap
(unless a reversed cmp function is being used, in which case it will be
the largest). Returns undef if the heap is empty.
This method used to be called "minimum" instead of
"top". The old name is still supported but is deprecated. (It
was confusing to use the method "minimum" to get the maximum
value on the heap when a reversed cmp function was used for ordering
elements.)
- $elem = $heap->extract_top
- Delete the top element from the heap and return it. Returns undef
if the heap was empty.
This method used to be called "extract_minimum" instead of
"extract_top". The old name is still supported but is
deprecated. (It was confusing to use the method
"extract_minimum" to get the maximum value on the heap when a
reversed cmp function was used for ordering elements.)
- $heap1->absorb($heap2)
- Merge all of the elements from $heap2 into $heap1. This will
leave $heap2 empty.
- $heap1->decrease_key($elem)
- The element will be moved closed to the top of the heap if it is now
smaller than any higher parent elements. The user must have changed the
value of $elem before decrease_key is called. Only a
decrease is permitted. (This is a decrease according to the cmp
function - if it is a reversed order comparison, then you are only
permitted to increase the value of the element. To be pedantic, you may
only use decrease_key if $elem-cmp($elem_original) <=
0> if $elem_original were an elem with the value that
$elem had before it was decreased.)
- $elem = $heap->delete($elem)
- The element is removed from the heap (whether it is at the top or
not).
AUTHOR¶
John Macdonald, john@perlwolf.com
COPYRIGHT¶
Copyright 1998-2007, O'Reilly & Associates.
This code is distributed under the same copyright terms as perl itself.
SEE ALSO¶
Heap::Elem(3),
Heap::Binary(3),
Heap::Binomial(3),
Heap::Fibonacci(3).