NAME
   Array::Heap - treat perl arrays as binary heaps/priority queues

SYNOPSIS
    use Array::Heap;

DESCRIPTION
   There are a multitude of heap and heap-like modules on CPAN, you might
   want to search for /Heap/ and /Priority/ to find many. They implement
   more or less fancy datastructures that might well be what you are
   looking for.

   This module takes a different approach: It exports functions (i.e. no
   object orientation) that are loosely modeled after the C++ STL's binary
   heap functions. They all take an array as argument, just like perl's
   built-in functions "push", "pop" etc.

   The implementation itself is in C for maximum speed.

FUNCTIONS
   All of the following functions are being exported by default.

   make_heap @heap (\@)
       Reorders the elements in the array so they form a heap, with the
       lowest value "on top" of the heap (corresponding to the first array
       element).

   make_heap_idx @heap (\@)
       Just like "make_heap", but updates the index (see INDEXED
       OPERATIONS).

   make_heap_lex @heap (\@)
       Just like "make_heap", but in string comparison order instead of
       numerical comparison order.

   make_heap_cmp { compare } @heap (&\@)
       Just like "make_heap", but takes a custom comparison function.

   push_heap @heap, $element, ... (\@@)
       Adds the given element(s) to the heap.

   push_heap_idx @heap, $element, ... (\@@)
       Just like "push_heap", but updates the index (see INDEXED
       OPERATIONS).

   push_heap_lex @heap, $element, ... (\@@)
       Just like "push_heap", but in string comparison order instead of
       numerical comparison order.

   push_heap_cmp { compare } @heap, $element, ... (&\@@)
       Just like "push_heap", but takes a custom comparison function.

   pop_heap @heap (\@)
       Removes the topmost (lowest) heap element and repairs the heap.

   pop_heap_idx @heap (\@)
       Just like "pop_heap", but updates the index (see INDEXED
       OPERATIONS).

   pop_heap_lex @heap (\@)
       Just like "pop_heap", but in string comparison order instead of
       numerical comparison order.

   pop_heap_cmp { compare } @heap (&\@)
       Just like "pop_heap", but takes a custom comparison function.

   splice_heap @heap, $index (\@$)
       Similar to "pop_heap", but removes and returns the element at index
       $index.

   splice_heap_idx @heap, $index (\@$)
       Just like "splice_heap", but updates the index (see INDEXED
       OPERATIONS).

   splice_heap_lex @heap, $index (\@$)
       Just like "splice_heap", but in string comparison order instead of
       numerical comparison order.

   splice_heap_cmp { compare } @heap, $index (&\@$)
       Just like "splice_heap", but takes a custom comparison function.

   adjust_heap @heap, $index (\@$)
       Assuming you have only changed the element at index $index, repair
       the heap again. Can be used to remove elements, replace elements,
       adjust the priority of elements and more.

   adjust_heap_idx @heap, $index (\@$)
       Just like "adjust_heap", but updates the index (see INDEXED
       OPERATIONS).

   adjust_heap_lex @heap, $index (\@$)
       Just like "adjust_heap", but in string comparison order instead of
       numerical comparison order.

   adjust_heap_cmp { compare } @heap, $index (&\@$)
       Just like "adjust_heap", but takes a custom comparison function.

 COMPARISON FUNCTIONS
   All the functions come in two flavours: one that uses the built-in
   comparison function and one that uses a custom comparison function.

   The built-in comparison function can either compare scalar numerical
   values (string values for *_lex functions), or array refs. If the
   elements to compare are array refs, the first element of the array is
   used for comparison, i.e.

     1, 4, 6

   will be sorted according to their numerical value,

     [1 => $obj1], [2 => $obj2], [3 => $obj3]

   will sort according to the first element of the arrays, i.e. "1,2,3".

   The custom comparison functions work similar to how "sort" works: $a and
   $b are set to the elements to be compared, and the result should be
   greater than zero then $a is greater than $b, 0 otherwise. This means
   that you can use the same function as for sorting the array, but you
   could also use a simpler function that just does "$a > $b".

   The first example above corresponds to this comparison "function":

     { $a <=> $b }

   And the second example corresponds to this:

     { $a->[0] <=> $b->[0] }

   Unlike "sort", the default sort is numerical and it is not possible to
   use normal subroutines.

 INDEXED OPERATIONS
   The functions whose names end in "_idx" also "update the index". That
   means that all elements must be array refs, with the first element being
   the heap value, and the second value being the array index:

     [$value, $index, ...]

   This allows you to quickly locate an element in the array when all you
   have is the array reference.

BUGS
   *   Numerical comparison is always done using floatingpoint, which
       usually has less precision than a 64 bit integer that perl might use
       for integers internally, resulting in precision loss on the built-in
       comparison.

   *   This module does not work with tied or magical arrays or array
       elements, and, in fact, will even crash when you use those.

   *   This module can leak memory (or worse) when your comparison function
       exits unexpectedly (e.g. "last") or throws an exception, so do not
       do that.

SEE ALSO
   This module has a rather low-level interface. If it seems daunting, you
   should have a look at Array::Heap::ModifiablePriorityQueue, which is
   based on this module but provides more and higher-level operations with
   an object-oriented API which makes it harder to make mistakes.

   A slightly less flexible (only numeric weights), but also slightly
   faster variant of that module can be found as
   Array::Heap::PriorityQueue::Numeric on CPAN.

AUTHOR AND CONTACT INFORMATION
    Marc Lehmann <[email protected]>
    http://software.schmorp.de/pkg/Array-Heap

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.