Scala で Binary heap tree [Scala]
何がきっかけで買おうと思ったのか不思議と全く思い出せないのだけど The fun of programming [1] という本が届いた（日本の Amazon には高いハードカバーしかなかったので出版元に直接注文して2週間くらいだった）ので、とりあえず第1章で紹介されている binary heap tree （のうち skew heap と呼ばれていたもの）を Scala で実装してみた。これは優先順位つきのキューに使える構造で、先頭要素（もっとも優先順位の高い要素）の参照は定数時間、取り出しと新規要素の追加は平均して対数時間（最悪で線形時間）という方式らしい。
abstract class BinaryHeapTree[T <% Ordered[T]] {
def isEmpty: Boolean
def top: T
def pop: BinaryHeapTree[T]
def insert(elem: T): BinaryHeapTree[T]
def merge(that: BinaryHeapTree[T]): BinaryHeapTree[T]
}
case class Empty[T <% Ordered[T]] extends BinaryHeapTree[T] {
def isEmpty = true
def top = error("Empty.top")
def pop = error("Empty.pop")
def insert(elem: T): BinaryHeapTree[T] = Fork(elem, Empty[T], Empty[T])
def merge(that: BinaryHeapTree[T]) = that
}
case class Fork[T <% Ordered[T]](label: T, left: BinaryHeapTree[T], right: BinaryHeapTree[T])
extends BinaryHeapTree[T] {
def isEmpty = false
def top = label
def pop = left.merge(right)
def insert(elem: T): BinaryHeapTree[T] = this.merge(Fork(elem, Empty[T], Empty[T]))
def merge(that: BinaryHeapTree[T]) = {
if (that.isEmpty) this
else if (this.top <= that.top) Fork(label, right, left.merge(that))
else that.merge(this)
}
}
object Main {
def main(args: Array[String]) = {
var t: BinaryHeapTree[Int] = Empty[Int]
for (i <- 1 to 7) {
t = t.insert(i)
Console.println(t)
}
}
}
いま悩んでいること：
- 関数的な構造なので variance annotation をつけて covariant な型付けをさせたいが、なんかうまくいかない。「 <% Ordered[T] 」がついているとそういうことはできないのかも。頭が整理できない。
コメント 8