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

NAME

6       Heap - Perl extensions for keeping data partially sorted
7

SYNOPSIS

9         use Heap;
10
11         my $heap = Heap->new;
12         my $elem;
13
14         use Heap::Elem::Num(NumElem);
15
16         foreach $i ( 1..100 ) {
17             $elem = NumElem( $i );
18             $heap->add( $elem );
19         }
20
21         while( defined( $elem = $heap->extract_top ) ) {
22             print "Smallest is ", $elem->val, "\n";
23         }
24

DESCRIPTION

26       The Heap collection of modules provide routines that manage a heap of
27       elements.  A heap is a partially sorted structure that is always able
28       to easily extract the smallest of the elements in the structure (or the
29       largest if a reversed compare routine is provided).
30
31       If the collection of elements is changing dynamically, the heap has
32       less overhead than keeping the collection fully sorted.
33
34       The elements must be objects as described in "Heap::Elem" and all
35       elements inserted into one heap must be mutually compatible - either
36       the same class exactly or else classes that differ only in ways
37       unrelated to the Heap::Elem interface.
38

METHODS

40       $heap = HeapClass::new(); $heap2 = $heap1->new();
41           Returns a new heap object of the specified (sub-)class.  This is
42           often used as a subroutine instead of a method, of course.
43
44       $heap->DESTROY
45           Ensures that no internal circular data references remain.  Some
46           variants of Heap ignore this (they have no such references).  Heap
47           users normally need not worry about it, DESTROY is automatically
48           invoked when the heap reference goes out of scope.
49
50       $heap->add($elem)
51           Add an element to the heap.
52
53       $elem = $heap->top
54           Return the top element on the heap.  It is not removed from the
55           heap but will remain at the top.  It will be the smallest element
56           on the heap (unless a reversed cmp function is being used, in which
57           case it will be the largest).  Returns undef if the heap is empty.
58
59           This method used to be called "minimum" instead of "top".  The old
60           name is still supported but is deprecated.  (It was confusing to
61           use the method "minimum" to get the maximum value on the heap when
62           a reversed cmp function was used for ordering elements.)
63
64       $elem = $heap->extract_top
65           Delete the top element from the heap and return it.  Returns undef
66           if the heap was empty.
67
68           This method used to be called "extract_minimum" instead of
69           "extract_top".  The old name is still supported but is deprecated.
70           (It was confusing to use the method "extract_minimum" to get the
71           maximum value on the heap when a reversed cmp function was used for
72           ordering elements.)
73
74       $heap1->absorb($heap2)
75           Merge all of the elements from $heap2 into $heap1.  This will leave
76           $heap2 empty.
77
78       $heap1->decrease_key($elem)
79           The element will be moved closed to the top of the heap if it is
80           now smaller than any higher parent elements.  The user must have
81           changed the value of $elem before decrease_key is called.  Only a
82           decrease is permitted.  (This is a decrease according to the cmp
83           function - if it is a reversed order comparison, then you are only
84           permitted to increase the value of the element.  To be pedantic,
85           you may only use decrease_key if $elem-cmp($elem_original) <= 0> if
86           $elem_original were an elem with the value that $elem had before it
87           was decreased.)
88
89       $elem = $heap->delete($elem)
90           The element is removed from the heap (whether it is at the top or
91           not).
92

AUTHOR

94       John Macdonald, john@perlwolf.com
95

97       Copyright 1998-2007, O'Reilly & Associates.
98
99       This code is distributed under the same copyright terms as perl itself.
100

SEE ALSO

102       Heap::Elem(3), Heap::Binary(3), Heap::Binomial(3), Heap::Fibonacci(3).
103
104
105
106perl v5.32.0                      2020-07-28                           Heap(3)
Impressum