NAME

Heap::Fibonacci::Fast - XS bridge to fast C fibonacci heap implementation

SYNOPSIS

        use Heap::Fibonacci::Fast;
        my $heap = Heap::Fibonacci::Fast->new();
        while(my ($key, $data) = compute()){
                $heap->key_insert($key, $data);
        }
        $heap->extract_top();
        
        my $heap = Heap::Fibonacci::Fast->new('code', sub { ord($a) <=> ord($b) });

DESCRIPTION

Heap is a data structure that keeps it's elements partially sorted, so when your data changes a lot, heaps are cheaper then maintaining fully sorted data.

METHODS

new

Initializes heap, with specific type. Default is 'min'. 'min' and 'max' types are keyed - with element, you should supply an integer key, that is used for ordering.

        my $heap = Heap::Fibonacci::Fast->new([$type, [$coderef]]);

min

This is default heap type. It is keyed, elements with minimal keys are extracted first.

max

This is keyed heap. Elements with maximal keys are extracted first.

code

This type is useful, when you can't specify exact keys for your elements, but, intead, allows you to compare elements by your own. Callback should use $a and $b, like standard sort, with same return values meanings.

insert

Adds all supplied elements to the heap. Can be used only for 'code' heaps. You can't store undef in the heap. If called in non-void context, then, for each added element, returns handle for usage with remove.

        my @handles = $heap->insert($elem1, ...);
        my $handle  = $heap->insert($data);

key_insert

Adds all supplied element+key pairs to the heap. Can be used only for keyed heaps. You can't store undef in the heap. If called in non-void context, then, for each added element, returns handle for usage with remove.

        my @handles = $heap->key_insert($key1, $elem1, ...);
        my $handle  = $heap->key_insert($key, $data);

extract_top

Remove top element of the heap (minimal one, in terms of comparsion function) and returns it. Returns undef for empty heap.

        my $elem = $heap->extract_top();

top

Returns top element of the heap (minimal one, in terms of comparsion function). Returns undef for empty heap.

        my $elem = $heap->top();

top_key

Returns key for the top element of the heap (minimal one, in terms of comparsion function). Returns undef for empty heap. Applicable only for keyed heaps.

        my $key = $heap->top_key();

extract_upto

Removes from heap and returns all elements that are smaller (in terms of comparsion function) than given key (for keyed heaps) or given element (for code heaps).

        my @elements = $heap->extract_upto(12);

remove

Removes element from heap, hanlde should be valid one, saved from insert/key_insert call. Handle for any particular element becomes invalid after clear, extract_top and extract_upto calls. Supplying invalind handle leads to unpredicatble results.

        $heap->remove($handle);

count

Returns number of elements in heap.

        my $count = $heap->count();

clear

Empties heap.

        $heap->clear();

get_type

Return heap type as string, same as for new call.

        if ($heap->get_type() ne 'code')

SEE ALSO

Heap

Pure-perl implementation of fibonacci, binary and binomial heaps, with rather strange interface.

Heap::Simple

Pure-perl and XS implementations of some heap (not specified heap's type), can handle supplied data in a variety of ways.

You can run compare.pl supplied with distribution to see some benchmark values.

http://en.wikipedia.org/wiki/Fibonacci_heap

Read this, if you want to know about Fibonacci heap algorythm complexity.

AUTHOR

Sergey Aleynikov <sergey.aleynikov@gmail.com>

LICENSE

Copyright (c) 2009 by Sergey Aleynikov. All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

libfib (c) 1997-2003 John-Mark Gurney, under the same terms. For full license text, see fib.c.

cpanm Heap::Fibonacci::Fast

perl -MCPAN -e shell
install Heap::Fibonacci::Fast