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

안녕하세요, Perl 6 Advent Calendar의 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"이 되었습니다.