On Apache
Under GNU General Public License
2024-04-23 05:06 @18.191.211.66 CrawledBy Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
Heap(3pm) User Contributed Perl Documentation Heap(3pm)
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 AT 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).
perl v5.22.1 2016-03-23 Heap(3pm)
Generated by $Id: phpMan.php,v 4.55 2007/09/05 04:42:51 chedong Exp $ Author: Che Dong
On Apache
Under GNU General Public License
2024-04-23 05:06 @18.191.211.66 CrawledBy Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)