NAME

       Heap - Perl extensions for keeping data partially sorted

SYNOPSIS

         use Heap;

         my $heap = Heap->new;
         my $elem;

         use Heap::Elem::Num(NumElem);

         foreach $i ( 1..100 ) {
             $elem = NumElem( $i );
             $heap->add( $elem );
         }

         while( defined( $elem = $heap->extract_top ) ) {
             print "Smallest is ", $elem->val, "\n";
         }

DESCRIPTION

       The Heap collection of modules provide routines that manage a heap of elements.  A heap is a partially
       sorted structure that is always able to easily extract the smallest of the elements in the structure (or
       the largest if a reversed compare routine is provided).

       If the collection of elements is changing dynamically, the heap has less overhead than keeping the
       collection fully sorted.

       The elements must be objects as described in "Heap::Elem" and all elements inserted into one heap must be
       mutually compatible - either the same class exactly or else classes that differ only in ways unrelated to
       the Heap::Elem interface.

METHODS

       $heap = HeapClass::new(); $heap2 = $heap1->new();
           Returns  a  new heap object of the specified (sub-)class.  This is often used as a subroutine instead
           of a method, of course.

       $heap->DESTROY
           Ensures that no internal circular data references remain.  Some variants of Heap  ignore  this  (they
           have  no  such  references).   Heap  users normally need not worry about it, DESTROY is automatically
           invoked when the heap reference goes out of scope.

       $heap->add($elem)
           Add an element to the heap.

       $elem = $heap->top
           Return the top element on the heap.  It is not removed from the heap but will remain at the top.   It
           will be the smallest element on the heap (unless a reversed cmp function is being used, in which case
           it will be the largest).  Returns undef if the heap is empty.

           This  method  used  to  be called "minimum" instead of "top".  The old name is still supported but is
           deprecated.  (It was confusing to use the method "minimum" to get the maximum value on the heap  when
           a reversed cmp function was used for ordering elements.)

       $elem = $heap->extract_top
           Delete the top element from the heap and return it.  Returns undef if the heap was empty.

           This  method  used  to  be  called "extract_minimum" instead of "extract_top".  The old name is still
           supported but is deprecated.  (It was confusing to  use  the  method  "extract_minimum"  to  get  the
           maximum value on the heap when a reversed cmp function was used for ordering elements.)

       $heap1->absorb($heap2)
           Merge all of the elements from $heap2 into $heap1.  This will leave $heap2 empty.

       $heap1->decrease_key($elem)
           The  element  will be moved closed to the top of the heap if it is now smaller than any higher parent
           elements.  The user must have changed the value of $elem  before  decrease_key  is  called.   Only  a
           decrease is permitted.  (This is a decrease according to the cmp function - if it is a reversed order
           comparison,  then  you  are only permitted to increase the value of the element.  To be pedantic, you
           may only use decrease_key if $elem-cmp($elem_original) <= 0> if $elem_original were an elem with  the
           value that $elem had before it was decreased.)

       $elem = $heap->delete($elem)
           The element is removed from the heap (whether it is at the top or not).

AUTHOR

       John Macdonald, john@perlwolf.com

COPYRIGHT

       Copyright 1998-2007, O'Reilly & Associates.

       This code is distributed under the same copyright terms as perl itself.

SEE ALSO

       Heap::Elem(3), Heap::Binary(3), Heap::Binomial(3), Heap::Fibonacci(3).

perl v5.10.0                                       2007-04-28                                          Heap(3pm)