Help language development. Donate to The Perl Foundation

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

README.md
[![Build Status](https://travis-ci.org/cono/p6-algorithm-heap-binary.svg?branch=master)](https://travis-ci.org/cono/p6-algorithm-heap-binary)

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.

  * empty constructor

        my $heap = Algorithm::Heap::Binary.new;

Default comparator is: `* <=> *`

  * named constructor

        my $heap = Algorithm::Heap::Binary.new(comparator => -> $a, $b {$b cmp $a});

  * constructor with heapify

        my @numbers = 1 .. *;
        my @letters = 'a' .. *;
        my @data = @numbers Z=> @letters;

        my $heap = Algorithm::Heap::Binary.new(comparator => * <=> *, |@data[^5]);

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](mailto:[email protected])

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

  * [https://en.wikipedia.org/wiki/Heap_(data_structure)](https://en.wikipedia.org/wiki/Heap_(data_structure))

  * [https://en.wikipedia.org/wiki/Binary_heap](https://en.wikipedia.org/wiki/Binary_heap)