Heap::Elem - Base class for elements in a Heap |
Heap::Elem - Base class for elements in a Heap
use Heap::Elem::SomeInheritor;
use Heap::SomeHeapClass;
$elem = Heap::Elem::SomeInheritor->new( $value ); $heap = Heap::SomeHeapClass->new;
$heap->add($elem);
This is an inheritable class for Heap Elements. It provides the interface documentation and some inheritable methods. Only a child classes can be used - this class is not complete.
The Heap processing routines use this method to map an element into its internal structure. This is needed to support the Heap methods that affect elements that are not are the top of the heap - decrease_key and delete.
The Heap processing routines will ensure that this value is
undef when this elem is removed from a heap, and is not undef
after it is inserted into a heap. This means that you can
check whether an element is currently contained within a heap
or not. (It cannot be used to determine which heap an element
is contained in, if you have multiple heaps. Keeping that
information accurate would make the operation of merging two
heaps into a single one take longer - it would have to traverse
all of the elements in the merged heap to update them; for
Binomial and Fibonacci heaps that would turn an O(1)
operation
into an O(n)
one.)
cmp($elem2)
This class can be inherited to provide an object with the ability to be heaped. If the object is implemented as a hash, and if it can deal with a key of heap, leaving it unchanged for use by the heap routines, then the following implemetation will work.
package myObject;
require Exporter;
@ISA = qw(Heap::Elem);
sub new { my $self = shift; my $class = ref($self) || $self;
my $self = SUPER::new($class);
# set $self->{key} = $value; }
sub cmp { my $self = shift; my $other = shift;
$self->{key} cmp $other->{key}; }
# other methods for the rest of myObject's functionality
John Macdonald, john@perlwolf.com
Copyright 1998-2007, O'Reilly & Associates.
This code is distributed under the same copyright terms as perl itself.
Heap(3), Heap::Elem::Num(3), Heap::Elem::NumRev(3), Heap::Elem::Str(3), Heap::Elem::StrRev(3).
Heap::Elem - Base class for elements in a Heap |