Heap::Elem(3pm)

1Elem(3)               User Contributed Perl Documentation              Elem(3)
2
3
4

NAME

6       Heap::Elem - Perl extension for elements to be put in Heaps
7

SYNOPSIS

9         use Heap::Elem::SomeInheritor;
10
11         use Heap::SomeHeapClass;
12
13         $elem = Heap::Elem::SomeInheritor->new( $value );
14         $heap = Heap::SomeHeapClass->new;
15
16         $heap->add($elem);
17

DESCRIPTION

19       This is an inheritable class for Heap Elements.  It provides the inter‐
20       face documentation and some inheritable methods.  Only a child classes
21       can be used - this class is not complete.
22

METHODS

24       $elem = Heap::Elem::SomeInheritor->new( [args] );
25           Creates a new Elem.
26
27       $elem->heap( $val ); $elem->heap;
28           Provides a method for use by the Heap processing routines.  If a
29           value argument is provided, it will be saved.  The new saved value
30           is always returned.  If no value argument is provided, the old
31           saved value is returned.
32
33           The Heap processing routines use this method to map an element into
34           its internal structure.  This is needed to support the Heap methods
35           that affect elements that are not are the top of the heap -
36           decrease_key and delete.
37
38           The Heap processing routines will ensure that this value is undef
39           when this elem is removed from a heap, and is not undef after it is
40           inserted into a heap.  This means that you can check whether an
41           element is currently contained within a heap or not.  (It cannot be
42           used to determine which heap an element is contained in, if you
43           have multiple heaps.  Keeping that information accurate would make
44           the operation of merging two heaps into a single one take longer -
45           it would have to traverse all of the elements in the merged heap to
46           update them; for Binomial and Fibonacci heaps that would turn an
47           O(1) operation into an O(n) one.)
48
49       $elem1->cmp($elem2)
50           A routine to compare two elements.  It must return a negative value
51           if this element should go higher on the heap than $elem2, 0 if they
52           are equal, or a positive value if this element should go lower on
53           the heap than $elem2.  Just as with sort, the Perl operators <=>
54           and cmp cause the smaller value to be returned first; similarly you
55           can negate the meaning to reverse the order - causing the heap to
56           always return the largest element instead of the smallest.
57

INHERITING

59       This class can be inherited to provide an oject with the ability to be
60       heaped.  If the object is implemented as a hash, and if it can deal
61       with a key of heap, leaving it unchanged for use by the heap routines,
62       then the following implemetation will work.
63
64         package myObject;
65
66         require Exporter;
67
68         @ISA = qw(Heap::Elem);
69
70         sub new {
71             my $self = shift;
72             my $class = ref($self) ⎪⎪ $self;
73
74             my $self = SUPER::new($class);
75
76             # set $self->{key} = $value;
77         }
78
79         sub cmp {
80             my $self = shift;
81             my $other = shift;
82
83             $self->{key} cmp $other->{key};
84         }
85
86         # other methods for the rest of myObject's functionality
87

AUTHOR

89       John Macdonald, jmm@perlwolf.com
90

COPYRIGHT

92       Copyright 1998-2003, O'Reilly & Associates.
93
94       This code is distributed under the same copyright terms as perl itself.
95