Heap - phpMan

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).