Marc Lehmann > Array-Heap2 > Array::Heap2

Download:
Array-Heap2-1.1.tar.gz

Dependencies

Annotate this POD

CPAN RT

Open  0
View/Report Bugs
Module Version: 1.1   Source  

NAME ^

Array::Heap2 - treat perl arrays as heaps (priority queues)

SYNOPSIS ^

 use Array::Heap2;

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. not object orientation) that are loosely modeled after the C++ STL's 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 (although I doubt it makes that much of a difference).

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

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 either -1 if $a is less than $b, or >= 0 otherwise.

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.

BUGS ^

This module works not work with tied or magical arrays or array elements.

AUTHOR ^

 Marc Lehmann <schmorp@schmorp.de>
 http://home.schmorp.de/
syntax highlighting: