home *** CD-ROM | disk | FTP | other *** search
/ PC Professionell 2004 December / PCpro_2004_12.ISO / files / webserver / tsw / TSW_3.4.0.exe / Apache2 / perl / Heap.pm < prev    next >
Encoding:
Perl POD Document  |  2003-12-04  |  4.1 KB  |  160 lines
  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
  160.