Algorithm::MinMaxHeap - A Raku implementation of double ended priority queue
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]
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;
has $.payload;
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]
Algorithm::MinMaxHeap is a simple implementation of double ended priority queue.
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;
$heap.insert($item);
Inserts an item to the queue.
my $max-value-item = $heap.pop-max();
Returns a maximum value item in the queue and deletes this item in the queue.
my $min-value-item = $heap.pop-min();
Returns a minimum value item in the queue and deletes this item in the queue.
my $max-value-item = $heap.find-max();
Returns a maximum value item in the queue.
my $min-value-item = $heap.find-min();
Returns a minimum value item in the queue.
while (not $heap.is-empty()) {
// YOUR CODE
}
Returns whether the queue is empty or not.
$heap.clear();
Deletes all items in the queue.
Don't insert both numerical items and stringified items into the same queue.
It will cause mixing of lexicographical order and numerical order.
titsuki titsuki@cpan.org
Copyright 2016 titsuki
This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.
This algorithm is from Atkinson, Michael D., et al. "Min-max heaps and generalized priority queues." Communications of the ACM 29.10 (1986): 996-1000.