A Perl 6 implementation of double ended priority queue <!-- [SEO] perl6 -->
Perl 6
Latest commit 453c535 May 30, 2017 @titsuki committed on GitHub Merge pull request #22 from titsuki/bump-version
Bump version to 0.13.2
Permalink
Failed to load latest commit information.
lib/Algorithm Make it more Perl6ish Dec 10, 2016
t Fix a typo Nov 27, 2016
.gitignore Initial commit Mar 13, 2016
.travis.yml Use zef instead of panda May 29, 2017
LICENSE Initial commit Mar 13, 2016
META6.json Bump version to 0.13.2 May 30, 2017
README.md Make it more Perl6ish Dec 10, 2016

README.md

Build Status

NAME

Algorithm::MinMaxHeap - A Perl 6 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;
   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]

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()) {
         // YOUR CODE
}

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 titsuki@cpan.org

COPYRIGHT AND LICENSE

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.