GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  HEAP (3)

.ds Aq ’

NAME

Heap - Perl extensions for keeping data partially sorted

CONTENTS

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 <B>Heap::ElemB> 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 <B>notB> 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).
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 HEAP (3) 2007-04-28

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.