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  -  ARRAY::HEAP (3)

.ds Aq ’

NAME

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

CONTENTS

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 cna 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

o 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.
o This module does not work with tied or magical arrays or array elements, and, in fact, will even crash when you use those.
o 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.

AUTHOR AND CONTACT INFORMATION



 Marc Lehmann <schmorp@schmorp.de>
 http://software.schmorp.de/pkg/Array-Heap



Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 HEAP (3) 2014-10-27

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