1Heap::Elem(3) User Contributed Perl Documentation Heap::Elem(3)
2
3
4
6 Heap::Elem - Base class for elements in a Heap
7
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
19 This is an inheritable class for Heap Elements. It provides the
20 interface documentation and some inheritable methods. Only a child
21 classes can be used - this class is not complete.
22
24 $elem = Heap::Elem::SomeInheritor->new( [args] );
25 Creates a new Elem. If there is exactly one arg, the Elem's value
26 will be set to that value. If there is more than one arg provided,
27 the Elem's value will be set to an anonymous hash initialized to
28 the provided args (which must have an even number, of course).
29
30 $elem->heap( $val ); $elem->heap;
31 Provides a method for use by the Heap processing routines. If a
32 value argument is provided, it will be saved. The new saved value
33 is always returned. If no value argument is provided, the old
34 saved value is returned.
35
36 The Heap processing routines use this method to map an element into
37 its internal structure. This is needed to support the Heap methods
38 that affect elements that are not are the top of the heap -
39 decrease_key and delete.
40
41 The Heap processing routines will ensure that this value is undef
42 when this elem is removed from a heap, and is not undef after it is
43 inserted into a heap. This means that you can check whether an
44 element is currently contained within a heap or not. (It cannot be
45 used to determine which heap an element is contained in, if you
46 have multiple heaps. Keeping that information accurate would make
47 the operation of merging two heaps into a single one take longer -
48 it would have to traverse all of the elements in the merged heap to
49 update them; for Binomial and Fibonacci heaps that would turn an
50 O(1) operation into an O(n) one.)
51
52 $elem->val( $val ); $elem->val;
53 Provides a method to get and/or set the value of the element.
54
55 $elem1->cmp($elem2)
56 A routine to compare two elements. It must return a negative value
57 if this element should go higher on the heap than $elem2, 0 if they
58 are equal, or a positive value if this element should go lower on
59 the heap than $elem2. Just as with sort, the Perl operators <=>
60 and cmp cause the smaller value to be returned first; similarly you
61 can negate the meaning to reverse the order - causing the heap to
62 always return the largest element instead of the smallest.
63
65 This class can be inherited to provide an object with the ability to be
66 heaped. If the object is implemented as a hash, and if it can deal
67 with a key of heap, leaving it unchanged for use by the heap routines,
68 then the following implemetation will work.
69
70 package myObject;
71
72 require Exporter;
73
74 @ISA = qw(Heap::Elem);
75
76 sub new {
77 my $self = shift;
78 my $class = ref($self) || $self;
79
80 my $self = SUPER::new($class);
81
82 # set $self->{key} = $value;
83 }
84
85 sub cmp {
86 my $self = shift;
87 my $other = shift;
88
89 $self->{key} cmp $other->{key};
90 }
91
92 # other methods for the rest of myObject's functionality
93
95 John Macdonald, john@perlwolf.com
96
98 Copyright 1998-2007, O'Reilly & Associates.
99
100 This code is distributed under the same copyright terms as perl itself.
101
103 Heap(3), Heap::Elem::Num(3), Heap::Elem::NumRev(3), Heap::Elem::Str(3),
104 Heap::Elem::StrRev(3).
105
106
107
108perl v5.28.1 2007-04-28 Heap::Elem(3)