Heap - Perl extensions for keeping data partially sorted |
Heap - Perl extensions for keeping data partially sorted
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"; }
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.
add($elem)
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.)
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.)
absorb($heap2)
decrease_key($elem)
cmp($elem_original)
<= 0> if $elem_original were
an elem with the value that $elem had before it was
decreased.)
delete($elem)
John Macdonald, john@perlwolf.com
Copyright 1998-2007, O'Reilly & Associates.
This code is distributed under the same copyright terms as perl itself.
Heap::Elem(3), Heap::Binary(3), Heap::Binomial(3), Heap::Fibonacci(3).
Heap - Perl extensions for keeping data partially sorted |