ScalaでimmutableなPriorityQueueを作ってみたよ
みんな大好きScalaですが、immutableなPriorityQueueが標準で無かったので試しに作ってみました。想定バージョンはScala 2.7.7です。
Immutable PriorityQueue in Scala — Gist
データ構造
今回は優先順位つきキューの実装に、Leftist Heapというヒープを使いました。これは左側の高さが右側よりもやや高くなるようにヒープを調整するもので、「Purely Functional Data Structures」ではかなり先頭のほうで紹介されている簡単なデータ構造です。だいたいの操作をO(log n)でやります。
ちなみにヒープというのは、親の要素が子よりも小さいような木構造のことです。
クラス構成
TreeSetやQueueの実装を見ながら、よりシンプルなクラス構成にしてみたらこうなりました。
関数型チックなデータ構造を作るときは、Scalaでは、「抽象クラスを用意して複数のケースクラスに継承させる」という手法がよく使える気がします。
- object PriorityQueue…ヒープ管理用の補助メソッドと、公開用のユーティリティーメソッドを用意しました。
- class PriorityQueue[A]…ヒープです。EmptyとTreeの2つのサブクラスが実装する抽象クラスです。Seq[A]を継承します。
- package priorityqueue
- case class Empty[A]…空のヒープです。
- case class Tree[A]…分岐です。自身の要素と2つのサブヒープを持ちます。
ヒープとして必要なmergeとかを実装したら、あとはSeq[A]を継承させて、必要なlength,apply,elementsなんかを実装しました。
で完成。
