Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | package Heap; |
2 | ||
3 | # heap is mainly here as documentation for the common heap interface. | |
4 | # It defaults to Heap::Fibonacci. | |
5 | ||
6 | use strict; | |
7 | use vars qw($VERSION @ISA @EXPORT @EXPORT_OK); | |
8 | ||
9 | require Exporter; | |
10 | require AutoLoader; | |
11 | ||
12 | @ISA = qw(Exporter AutoLoader); | |
13 | ||
14 | # No names exported. | |
15 | # No names available for export. | |
16 | @EXPORT = ( ); | |
17 | ||
18 | $VERSION = '0.70'; | |
19 | ||
20 | ||
21 | # Preloaded methods go here. | |
22 | ||
23 | sub new { | |
24 | use Heap::Fibonacci; | |
25 | ||
26 | return &Heap::Fibonacci::new; | |
27 | } | |
28 | ||
29 | # Autoload methods go after =cut, and are processed by the autosplit program. | |
30 | ||
31 | 1; | |
32 | __END__ | |
33 | # Below is the stub of documentation for your module. You better edit it! | |
34 | ||
35 | =head1 NAME | |
36 | ||
37 | Heap - Perl extensions for keeping data partially sorted | |
38 | ||
39 | =head1 SYNOPSIS | |
40 | ||
41 | use Heap; | |
42 | ||
43 | my $heap = Heap->new; | |
44 | my $elem; | |
45 | ||
46 | use Heap::Elem::Num(NumElem); | |
47 | ||
48 | foreach $i ( 1..100 ) { | |
49 | $elem = NumElem( $i ); | |
50 | $heap->add( $elem ); | |
51 | } | |
52 | ||
53 | while( defined( $elem = $heap->extract_maximum ) ) { | |
54 | print "Smallest is ", $elem->val, "\n"; | |
55 | } | |
56 | ||
57 | =head1 DESCRIPTION | |
58 | ||
59 | The Heap collection of modules provide routines that manage | |
60 | a heap of elements. A heap is a partially sorted structure | |
61 | that is always able to easily extract the smallest of the | |
62 | elements in the structure (or the largest if a reversed compare | |
63 | routine is provided). | |
64 | ||
65 | If the collection of elements is changing dynamically, the | |
66 | heap has less overhead than keeping the collection fully | |
67 | sorted. | |
68 | ||
69 | The elements must be objects as described in L<"Heap::Elem"> | |
70 | and all elements inserted into one heap must be mutually | |
71 | compatible - either the same class exactly or else classes that | |
72 | differ only in ways unrelated to the B<Heap::Elem> interface. | |
73 | ||
74 | =head1 METHODS | |
75 | ||
76 | =over 4 | |
77 | ||
78 | =item $heap = HeapClass::new(); $heap2 = $heap1->new(); | |
79 | ||
80 | Returns a new heap object of the specified (sub-)class. | |
81 | This is often used as a subroutine instead of a method, | |
82 | of course. | |
83 | ||
84 | =item $heap->DESTROY | |
85 | ||
86 | Ensures that no internal circular data references remain. | |
87 | Some variants of Heap ignore this (they have no such references). | |
88 | Heap users normally need not worry about it, DESTROY is automatically | |
89 | invoked when the heap reference goes out of scope. | |
90 | ||
91 | =item $heap->add($elem) | |
92 | ||
93 | Add an element to the heap. | |
94 | ||
95 | =item $elem = $heap->top | |
96 | ||
97 | Return the top element on the heap. It is B<not> removed from | |
98 | the heap but will remain at the top. It will be the smallest | |
99 | element on the heap (unless a reversed cmp function is being | |
100 | used, in which case it will be the largest). Returns I<undef> | |
101 | if the heap is empty. | |
102 | ||
103 | This method used to be called "minimum" instead of "top". The | |
104 | old name is still supported but is deprecated. (It was confusing | |
105 | to use the method "minimum" to get the maximum value on the heap | |
106 | when a reversed cmp function was used for ordering elements.) | |
107 | ||
108 | =item $elem = $heap->extract_top | |
109 | ||
110 | Delete the top element from the heap and return it. Returns | |
111 | I<undef> if the heap was empty. | |
112 | ||
113 | This method used to be called "extract_minimum" instead of | |
114 | "extract_top". The old name is still supported but is deprecated. | |
115 | (It was confusing to use the method "extract_minimum" to get the | |
116 | maximum value on the heap when a reversed cmp function was used | |
117 | for ordering elements.) | |
118 | ||
119 | =item $heap1->absorb($heap2) | |
120 | ||
121 | Merge all of the elements from I<$heap2> into I<$heap1>. | |
122 | This will leave I<$heap2> empty. | |
123 | ||
124 | =item $heap1->decrease_key($elem) | |
125 | ||
126 | The element will be moved closed to the top of the | |
127 | heap if it is now smaller than any higher parent elements. | |
128 | The user must have changed the value of I<$elem> before | |
129 | I<decrease_key> is called. Only a decrease is permitted. | |
130 | (This is a decrease according to the I<cmp> function - if it | |
131 | is a reversed order comparison, then you are only permitted | |
132 | to increase the value of the element. To be pedantic, you | |
133 | may only use I<decrease_key> if | |
134 | I<$elem->cmp($elem_original) <= 0> if I<$elem_original> were | |
135 | an elem with the value that I<$elem> had before it was | |
136 | I<decreased>.) | |
137 | ||
138 | =item $elem = $heap->delete($elem) | |
139 | ||
140 | The element is removed from the heap (whether it is at | |
141 | the top or not). | |
142 | ||
143 | =back | |
144 | ||
145 | =head1 AUTHOR | |
146 | ||
147 | John Macdonald, jmm@perlwolf.com | |
148 | ||
149 | =head1 COPYRIGHT | |
150 | ||
151 | Copyright 1998-2003, O'Reilly & Associates. | |
152 | ||
153 | This code is distributed under the same copyright terms as perl itself. | |
154 | ||
155 | =head1 SEE ALSO | |
156 | ||
157 | Heap::Elem(3), Heap::Binary(3), Heap::Binomial(3), Heap::Fibonacci(3). | |
158 | ||
159 | =cut |