| 1 |
Heap routines... |
| 2 |
|
| 3 |
This is a collection of routines for managing a heap data structure. |
| 4 |
|
| 5 |
There are two major components: a heap component, and an element |
| 6 |
component. |
| 7 |
|
| 8 |
A heap package basically keeps a collection of elements and is |
| 9 |
able to return the smallest one. |
| 10 |
|
| 11 |
The heap component interface is defined in Heap(3) and must be |
| 12 |
supported by all heap packages. Currently there are three heap |
| 13 |
components provided: |
| 14 |
|
| 15 |
Heap::Fibonacci (the preferred one) |
| 16 |
Heap::Binomial |
| 17 |
Heap::Binary |
| 18 |
|
| 19 |
See the book "Algorithms" by Cormen, Leiserson, and Rivest for |
| 20 |
details of the three heap packages. |
| 21 |
|
| 22 |
The element package wraps the data that is to be stored and retrieved |
| 23 |
on the heap. You can inherit from the Heap::Elem object to embed |
| 24 |
element capability into your own objects, or you can use the provided |
| 25 |
objects to embed your data into elements without having to |
| 26 |
specifically design your dat for that purpose. The Heap::Elem(3) |
| 27 |
module provides a detailed description of the requirements of an |
| 28 |
element module. (The main ones are that it must provide a cmp method |
| 29 |
so that the elements can be ordered, and it must provide a heap |
| 30 |
method that will either store or retrieve a scalar value so that the |
| 31 |
heap routines can map an element reference into its position within |
| 32 |
the heap. |
| 33 |
|
| 34 |
Version 0.70 was used for the graph routines in the book "Mastering |
| 35 |
Algorithms with Perl", and there has been some feedback from users, |
| 36 |
which indicates that it is not too rough around the edges. |
| 37 |
|
| 38 |
Comments to: |
| 39 |
|
| 40 |
John Macdonald <[email protected]> |
| 41 |
|
| 42 |
Copyright: |
| 43 |
|
| 44 |
This code is copyright 1998-2007 O'Reilly & Associates. It is |
| 45 |
available on the same terms as perl itself. |