Help language development. Donate to The Perl Foundation

Algorithm::Heap::Binary cpan:CONO last updated on 2018-05-05

Algorithm-Heap-Binary-0.0.1/

Build Status

NAME

Algorithm::Heap::Binary - Implementation of a BinaryHeap

SYNOPSIS

    use Algorithm::Heap::Binary;

    my Algorithm::Heap::Binary $heap .= new(
        comparator => * <=> *,
        3 => 'c',
        2 => 'b',
        1 => 'a'
    );

    $heap.size.say; # 3

    # heap-sort example
    $heap.delete-min.value.say; # a
    $heap.delete-min.value.say; # b
    $heap.delete-min.value.say; # c

DESCRIPTION

Algorithm::Heap::Binary provides to you BinaryHeap data structure with basic heap operations defined in Algorithm::Heap role:

peek

find a maximum item of a max-heap, or a minimum item of a min-heap, respectively

push

returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap

pop

removing the root node of a max heap [or min heap]

replace

pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps

is-empty

return true if the heap is empty, false otherwise

size

return the number of items in the heap

merge

joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps

METHODS

Constructor

BinaryHeap contains Pair objects and define order between Pair.key by the comparator. Comparator - is a Code which defines how to order elements internally. With help of the comparator you can create Min-heap or Max-heap.

Default comparator is: * <=> *

This will automatically heapify data for you.

clone

Clones heap object for you with all internal data.

is-empty

Returns Bool result as to empty Heap or not.

size

Returns Int which corresponds to amount elements in the Heap data structure.

push(Pair)

Adds new Pair to the heap and resort it.

insert(Pair)

Alias for push method.

peek

Returns Pair from the top of the Heap.

find-max

Just an syntatic alias for peek method.

find-min

Just an syntatic alias for peek method.

pop

Returns Piar from the top of the Heap and also removes it from the Heap.

delete-max

Just an syntatic alias for pop method.

delete-min

Just an syntatic alias for pop method.

replace(Pair)

Replace top element with another Pair. Returns replaced element as a result.

merge(Algorithm::Heap)

Construct a new Heap merging current one and passed to as an argument.

Seq

Returns Seq of Heap elements. This will clone the data for you, so initial data structure going to be untouched.

Str

Prints internal representation of the Heap (as an Array).

iterator

Method wich provides iterator (role Iterable). Will clone current Heap for you.

sift-up

Internal method to make sift-up operation.

sift-down

Internal method to make sift-down operation.

AUTHOR

cono

COPYRIGHT AND LICENSE

Copyright 2018 cono

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.

LINKS