use vars
qw($VERSION @ISA @EXPORT @EXPORT_OK);
@ISA = qw(Exporter AutoLoader);
# No names available for export.
# Preloaded methods go here.
# i - index of a heap value element
# v - user-provided value (to be) stored on the heap
################################################# debugging control
# enable/disable debugging output
@_ ?
($debug = shift) : $debug;
# enable/disable validation checks on values
@_ ?
($validate = shift) : $validate;
$width = 2 if $width < 2;
$bar = $corner = ' ' x
$width;
substr($corner,-2,2) = '+-';
my $space = ' ' x
$width;
printf( "%${width}d", $h->[$i]->val );
hdump
( $h, $ch, $p . $bar);
hdump
( $h, $ch, $p . $space );
for( $p = 0, $i = 1; $i < @
$h; ++$p, ++$i ) {
$h->[$p]->cmp($h->[$i]) <= 0 or die "not in heap order";
$h->[$p]->cmp($h->[$i]) <= 0 or die "not in heap order";
heapdump
$h if $validate >= 2;
################################################# forward declarations
################################################# heap methods
# new() usually Heap::Binary->new()
# return a new empty heap
my $class = ref($self) || $self;
# add($h,$v) usually $h->add($v)
# insert value $v into the heap
die "Method 'heap' required for element on heap"
die "Method 'cmp' required for element on heap"
heapup
$h, scalar(@
$h), $v;
# top($h) usually $h->top
# the smallest value is returned, but it is still left on the heap
# extract_top($h) usually $h->extract_top
# the smallest value is returned after removing it from the heap
# there was at least one item, must decrease the heap
# $top was not the only thing left, so re-heap the
# remainder by over-writing position zero (where
# $top was) using the value popped from the end
*extract_minimum
= \
&extract_top
;
# absorb($h,$h2) usually $h->absorb($h2)
# all of the values in $h2 are inserted into $h instead, $h2 is left
foreach $v (splice @
$h2, 0) {
# decrease_key($h,$v) usually $h->decrease_key($v)
# the key value of $v has just been decreased and so it may need to
# be percolated to a higher position in the heap
die "Method 'heap' required for element on heap"
die "Method 'cmp' required for element on heap"
# delete($h,$v) usually: $h->delete($v)
# delete value $v from heap $h. It must have previously been
die "Method 'heap' required for element on heap"
die "Method 'cmp' required for element on heap"
return $v unless defined $i;
################################################# internal utility functions
# place value $v at index $i in the heap $h, and update it record
# value $v is to be placed at index $i in heap $h, but it might
# be smaller than some of its parents. Keep pushing parents down
# until a smaller parent is found or the top of the heap is reached,
# and then place $v there.
while( $i && $v->cmp($h->[$pi = int( ($i-1)/2 )]) < 0 ) {
moveto
$h, $i, $h->[$pi];
# value $v is to be placed at index $i in heap $h, but it might
# have children that are smaller than it is. Keep popping the smallest
# child up until a pair of larger children is found or a leaf node is
# reached, and then place $v there.
$j = $k if $k < @
$h && $h->[$k]->cmp($h->[$j]) < 0;
if( $v->cmp($h->[$j]) > 0 ) {
Heap::Binary - a Perl extension for keeping data partially sorted
$heap = Heap::Binary->new;
Keeps an array of elements in heap order. The I<heap> method
of an element is used to store the index into the array that
See L<Heap> for details on using this module.
John Macdonald, jmm@perlwolf.com
Copyright 1998-2003, O'Reilly & Associates.
This code is distributed under the same copyright terms as perl itself.