窓口係のトリアージ

ヒープとは、常に最小の要素を把握していて、その要素をすばやく取り出せるコレクションです。優先度付きキューにうってつけの道具でもあります。優先度付きキューとは、最も長く待ったものではなく、最も重要なものが次に処理される待ち行列のことです。ヒープはheapsボキャブラリーにあります。

ヒープを作る

<min-heap>は、最小のキーが最初に出てくる空のヒープを作ります。<max-heap>はその鏡写しです。

<min-heap> ( -- min-heap )
<max-heap> ( -- max-heap )

要素を追加する

各要素は値とキーの組として格納されます。キーはFactorが順序付けに使う優先度です。heap-pushで1つ追加します。

heap-push ( value key heap -- )

USING: heaps ;

<min-heap>
"alice" 5 pick heap-push   ! value "alice", priority 5
"bob"   2 pick heap-push   ! value "bob",   priority 2

ヒープは変更可能です。heap-pushは新しいヒープを返すのではなく、その場でヒープを書き換えます。heap-pushがヒープを消費したあとに、そのヒープをスタックに戻したいときはkeepが便利です。

先頭を見る、取り出す

heap-peekは先頭の要素、つまり最小のキーを持つ値を、取り出さずに返します。heap-popはその要素を返し、さらに取り除きます。heap-empty?は何か残っているかどうかを報告するので、いつ取り出すのをやめればよいかがわかります。heap-pop-allはすべてを一度に取り除き、優先度順に並んだ{ key value }ペアの連想リストを返します。

heap-peek    ( heap -- value key )
heap-pop     ( heap -- value key )
heap-empty?  ( heap -- ? )
heap-pop-all ( heap -- alist )

USING: assocs heaps kernel prettyprint ;

<min-heap>
"alice" 5 pick heap-push
"bob"   2 pick heap-push
dup heap-empty? .        ! => f      (two items waiting)
dup heap-peek drop .     ! => "bob"  (smallest key, still in the heap)
dup heap-pop drop .      ! => "bob"  (smallest key, now removed)
heap-pop-all .           ! => { { 5 "alice" } }

heap-popとheap-empty?は、要素を1つずつ処理していくための部品です。先頭を覗くか取り出すかして、それに対して処理を行い、heap-empty?がtを返したらやめます。以下のタスクではheap-pop-allを使ってキュー全体を一度に空にしますが、ヒープが空になるまで取り出し続けても同じ順序になります。

heap-pop-allから得られるペアは連想リストです。assocsにあるvaluesを使うと、キーを捨てて値だけを取り出せます。