heap(3)
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_maximum ) ) {
print "Smallest is ", $elem->val, "0;
}
DESCRIPTION
The Heap collection of modules provide routines that man
age a heap of elements. A heap is a partially sorted
structure that is always able to easily extract the small
est 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->minimum
- 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. - $elem = $heap->extract_minimum
- Delete the top element from the heap and return it.
Returns undef if the heap was empty. - $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 ele
ments. 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, jmm@elegant.com
COPYRIGHT
Copyright 1998, O'Reilly & Associates.
This code is distributed under the same copyright terms as
perl itself.