man > Heap

Heap(3pm)                        User Contributed Perl Documentation                       Heap(3pm)

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 AT 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.36.0                                 2022-10-22                                    Heap(3pm)