Let's learn and try double-ended priority queue with Perl 6 #algorithm

こんにちは、Perl 6アドベントカレンダーの9日目の投稿になります。

今日は、拙作Algorithm::MinMaxHeapの紹介をしたいと思います。

Introduction

Algorithm::MinMaxHeap はdouble-ended priority queueの実装です。[0]

一つの木構造の中に、降順と昇順の2種類のヒープが同時に入っているという、ちょっとおもしろいデータ構造をしています。
もう少し正確な言葉で言い換えると、これはノードがMin-Maxオーダーになっている木です：

偶数段目(図のMin level)にあるノードは、同じ偶数段目にある子のノードと値が同じかそれよりも小さくなっています。
奇数段目(図のMax level)にあるノードは、同じ奇数段目にある子のノードと値が同じかそれよりも大きくなっています。

MinMaxHeap Internals

代表的なメソッド(e.g. insert, pop)について、内部でこれらのメソッドが行っていることを簡単に説明します。
Min-Maxオーダーを維持しつつinsertやpopを行うために下記のような操作が行われています。：

insert:

ヒープの末尾にノードをプッシュする
プッシュしたところからルートへ向かっていき、もしもMin-Maxオーダーを崩しているノードを見つけたら (※)、崩れないようにノードをスワップするという操作を繰り返す(※)

pop-max:

Max levelのノードのうち一番値の大きい要素を抜き、ヒープの中で一番最後のノードで抜けたところを埋める
埋めたところから葉の方向へ向かっていき、もしもMin-Maxオーダーを崩しているノードを見つけたら、崩れないようにノードをスワップするという操作を繰り返す(※)

pop-min:

Min levelのノードのうち一番値の小さい要素を抜き、ヒープの中で一番最後のノードで抜けたところを埋める
埋めたところから葉の方向へ向かっていき、もしもMin-Maxオーダーを崩しているノードを見つけたら、崩れないようにノードをスワップするという操作を繰り返す(※)

(※) わかりやすくするために、だいぶ簡潔に表現しました。正確な操作を知りたい場合はちゃんと論文を読んでください。

Let's try !

では、実際に使ってみましょう。

一番簡単な例を紹介すると、もちろん、ごく普通にInt型の値をノードとしたdouble-ended priority queueを作ることができます：

basic.p6

use Algorithm::MinMaxHeap;

my Algorithm::MinMaxHeap[Int] $heap .= new;
my Int @items = (^10).pick(*);
@items.say;                       # [1 2 6 4 5 9 0 3 7 8]                                                            
$heap.insert($_) for @items;
$heap.pop-max.say; # 9

また、subsetを使って複雑な型の制約を自分で定義することもできます。
下記の例ではCool型のサブクラスでRatかNumしか使えないという制約のChimeraRat型を定義しています：

chimera.p6

use Algorithm::MinMaxHeap;

my subset ChimeraRat of Cool where Num|Rat;
my Algorithm::MinMaxHeap[ChimeraRat] $heap .= new;

$heap.insert(10e0); # ok                                                                                             
$heap.insert(1/10); # ok                                                                                             
$heap.insert(10); # die

下記のように Int型の10を代入したときに、きちんとエラーメッセージを出して終了できるようになります：

実行結果

$ perl6 chimera.p6
Type check failed in assignment to @!nodes; expected ChimeraRat but got Int (10)
  in method insert at /home/itoyota/.rakudobrew/moar-nom/install/share/perl6/site/sources/240192C19BBAACD01AB9686EE53F67BC530F8545 (Algorithm::MinMaxHeap) line 12
  in block <unit> at 01.p6 line 8

ユーザー定義のクラスのインスタンスをdouble-ended priority queueに入れることもできます：

class.p6

use Algorithm::MinMaxHeap;

my class State {
    also does Algorithm::MinMaxHeap::Comparable[State];
    has DateTime $.time;
    has $.payload;
    submethod BUILD(:$!time, :$!payload) { }
    method compare-to(State $s) {
        if $!time == $s.time {
            return Order::Same;
        }
        if $!time > $s.time {
            return Order::More;
        }
        if $!time < $s.time {
            return Order::Less;
        }
    }
}

my State @items;
@items.push(State.new(time => DateTime.new(:year(1900), :month(6)),
                      payload => "Rola"));
@items.push(State.new(time => DateTime.new(:year(-300), :month(3)),
                      payload => "Taro"));
@items.push(State.new(time => DateTime.new(:year(1963), :month(12)),
                      payload => "Hanako"));
@items.push(State.new(time => DateTime.new(:year(2020), :month(6)),
                      payload => "Jack"));

my Algorithm::MinMaxHeap[Algorithm::MinMaxHeap::Comparable] $heap .= new;
$heap.insert($_) for @items;
$heap.pop-max.say until $heap.is-empty;

実行結果

$ perl6 class.p6
State.new(time => DateTime.new(2020,6,1,0,0,0), payload => "Jack")
State.new(time => DateTime.new(1963,12,1,0,0,0), payload => "Hanako")
State.new(time => DateTime.new(1900,6,1,0,0,0), payload => "Rola")
State.new(time => DateTime.new(-300,3,1,0,0,0), payload => "Taro")

References

Atkinson, Michael D., et al. "Min-max heaps and generalized priority queues." Communications of the ACM 29.10 (1986): 996-1000.

以上、9日目の投稿、"Let's learn and try double-ended priority queue with Perl 6"になりました。