Help language development. Donate to The Perl Foundation

Algorithm::MinMaxHeap cpan:TITSUKI last updated on 2020-06-20

Algorithm-MinMaxHeap-0.13.5/

NAME

Algorithm::MinMaxHeap - A Raku implementation of double ended priority queue

SYNOPSIS

EXAMPLE1

``````use Algorithm::MinMaxHeap;

my \$heap = Algorithm::MinMaxHeap[Int].new;
\$heap.insert(0);
\$heap.insert(1);
\$heap.insert(2);
\$heap.insert(3);
\$heap.insert(4);
\$heap.insert(5);
\$heap.insert(6);
\$heap.insert(7);
\$heap.insert(8);

\$heap.find-max.say # 8;
\$heap.find-min.say # 0;

my @array;
@array.push(\$heap.pop-max) until \$heap.is-empty;
@array.say # [8, 7, 6, 5, 4, 3, 2, 1, 0]
``````

EXAMPLE2

``````use Algorithm::MinMaxHeap;
use Algorithm::MinMaxHeap::Comparable;

# sets compare-to method using Algorithm::MinMaxHeap::Comparable role
my class State {
also does Algorithm::MinMaxHeap::Comparable[State];
has Int \$.value;
submethod BUILD(:\$!value) { }
method compare-to(State \$s) {
if \$!value == \$s.value {
return Order::Same;
}
if \$!value > \$s.value {
return Order::More;
}
if \$!value < \$s.value {
return Order::Less;
}
}
}

# specify Algorithm::MinMaxHeap::Comparable role as an item type
my \$class-heap = Algorithm::MinMaxHeap[Algorithm::MinMaxHeap::Comparable].new;
\$class-heap.insert(State.new(value => 0));
\$class-heap.insert(State.new(value => 1));
\$class-heap.insert(State.new(value => 2));
\$class-heap.insert(State.new(value => 3));
\$class-heap.insert(State.new(value => 4));
\$class-heap.insert(State.new(value => 5));
\$class-heap.insert(State.new(value => 6));
\$class-heap.insert(State.new(value => 7));
\$class-heap.insert(State.new(value => 8));

\$class-heap.find-max.value.say # 8;
\$class-heap.find-min.value.say # 0;

my @array;
until \$class-heap.is-empty {
my \$state = \$class-heap.pop-max;
@array.push(\$state.value);
}
@array.say # [8, 7, 6, 5, 4, 3, 2, 1, 0]
``````

DESCRIPTION

Algorithm::MinMaxHeap is a simple implementation of double ended priority queue.

CONSTRUCTOR

Defined as:

``````role Algorithm::MinMaxHeap[::Type] {}
``````

Usage:

``````my \$heap = Algorithm::MinMaxHeap[Int].new;
my \$heap = Algorithm::MinMaxHeap[Rat].new;
my \$heap = Algorithm::MinMaxHeap[Algorithm::MinMaxHeap::Comparable].new;
``````

Sets `::Type` parameter, where `::Type` is a type of nodes in the queue.

Use `subset` for creating complex type constraints:

``````my subset MyCool of Cool where Int|Num|Rat;
my \$heap = Algorithm::MinMaxHeap[MyCool].new;
``````

METHODS

insert(\$item)

``````\$heap.insert(\$item);
``````

Inserts an item to the queue.

pop-max()

``````my \$max-value-item = \$heap.pop-max();
``````

Returns a maximum value item in the queue and deletes this item in the queue.

pop-min()

``````my \$min-value-item = \$heap.pop-min();
``````

Returns a minimum value item in the queue and deletes this item in the queue.

find-max()

``````my \$max-value-item = \$heap.find-max();
``````

Returns a maximum value item in the queue.

find-min()

``````my \$min-value-item = \$heap.find-min();
``````

Returns a minimum value item in the queue.

is-empty() returns Bool:D

``````while (not \$heap.is-empty()) {
}
``````

Returns whether the queue is empty or not.

clear()

``````\$heap.clear();
``````

Deletes all items in the queue.

CAUTION

Don't insert both numerical items and stringified items into the same queue.

It will cause mixing of lexicographical order and numerical order.

AUTHOR

titsuki [email protected]