「ヒープ (heap)」は「半順序木 (partial ordered tree)」と呼ばれる木構造の一種で、普通は二分木を使った二分ヒープのことを指します。ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (n) の対数 (log2 n) に比例する程度の時間で済みます。
ヒープは配列を使って簡単に実装することができます。また、二分木を使ったヒープの実装では Leftist Heap と Skew Heap というアルゴリズムがあります。配列の操作は副作用を伴うので、immutable なヒープが必要な場合は Leftist Heap や Skew Heap を使う方が良いでしょう。
Leftist Heap や Skew Heap については拙作のページ「お気楽 Haskell プログラミング入門」の「ヒープ (2)」をお読みください。今回は配列によるヒープの実装を説明します。
一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きい、という関係を満たすように作ります。「半順序木」の場合、親は子より小さいか等しい、という関係を満たすように作ります。このとき、葉はすべて同じ高さになるか、そうでなければ、葉は左から右へ順番に埋めていきます。
このような二分木は配列で表すことができます。ヒープの場合、木の根を配列の添字 0 とすると、0 番目には必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。
0 1 2 3 4 5 6
TABLE [10 20 30 40 50 60 70]
(root)
10 (0)
／ ＼ 親の添字を k とすると
／ ＼ その子は 2*k+1, 2*k+2 になる。
20 (1) 30 (2) 子の添字を k とすると
／ ＼ ／ ＼ その親は (k - 1) / 2 になる。
40 50 60 70 親の値 <= 子の値 の関係を満たす。
(3) (4) (5) (6)
図 : ヒープと配列の対応関係
ヒープは、下図の手順で作ることができます。まず、データを最後尾に追加します。そして、このデータがヒープの条件を満たしているかチェックします。もしも、条件を満たしていなければ、親と子を入れ換えて、次の親をチェックします。これを木のルート方向 (添字 0 の方向) に向かって繰り返します。条件を満たすか、木のルート (添字 0) まで到達すれば、処理を終了します。これをデータの個数だけ繰り返します。
TABLE [＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 最初は空
[80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 最初のデータをセット
[80 10 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 次のデータをセットし親と比較
親 子 親の位置 0 = (1 - 1)/2
[10 80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 順序が違っていたら交換
[10 80 60 ＊ ＊ ＊ ＊ ＊ ＊ ＊] データをセットし比較
親 子 親の位置 0 = (2 - 1)/2
[10 80 60 20 ＊ ＊ ＊ ＊ ＊ ＊] データをセットし比較
親 子 親の位置 1 = (3 - 1)/2
[10 20 60 80 ＊ ＊ ＊ ＊ ＊ ＊] 交換する
・・・・データがなくなるまで繰り返す・・・・
図 : ヒープの構築 (1)
このアルゴリズムを Scala でプログラムすると、次のようになります。
リスト : ヒープの構築 (1)
import scala.collection.mutable.{ArrayBuffer}
import scala.math.Ordered.orderingToOrdered
class Heap[A] {
private val buff = new ArrayBuffer[A]
// ヒープの構築
private def upheap(n: Int)(implicit f: A => Ordered[A]): Unit = {
if (n > 0) {
val p = (n - 1) / 2
if (buff(p) > buff(n)) {
val tmp = buff(p)
buff(p) = buff(n)
buff(n) = tmp
upheap(p)
}
}
}
//
// メソッドの定義 (省略)
//
}
配列は ArrayBuffer を使います。関数 upheap はヒープを満たすように n 番目の要素をルート方向に向かって移動させます。0 から n - 1 番目までの要素はヒープの条件を満たしているとします。n が 0 の場合、ルートまでたどったので処理を終了します。n の親を p とすると、p は (n - 1) / 2 で求めることができます。そして、親 p が子 n よりも大きい場合、ヒープの条件を満たさないので p 番目と n 番目の要素を交換し、upheap を再帰呼び出しして次の親子関係をチェックします。そうでなければ、ヒープの条件を満たしているので処理を終了します。
実際にヒープを構築する場合は、配列の最後尾にデータを追加して、upheap を呼び出せばいいわけです。また、n 個のデータが格納されている配列でも、upheap を n - 1 回呼び出せばヒープを構築することができます。ただし、これはそれほど速い方法ではありません。もう少し高速な方法はあとで説明することにしましょう。
次は、最小値を取り出したあとで新しいデータを追加し、ヒープを再構築する手順を説明します。下図を見てください。
最初に、ヒープの最小値である添字 0 の位置にあるデータを取り出します。次に、その位置に新しいデータをセットし、ヒープの条件を満たしているかチェックします。ヒープの構築とは逆に、葉の方向 (添字の大きい方向) に向かってチェックしていきます。
まず、2 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。
TABLE [10 20 30 40 50 60 70 80 90 100] ヒープを満たしている
[＊ 20 30 40 50 60 70 80 90 100] 最小値を取り出す
[66 20 30 40 50 60 70 80 90 100] 新しい値をセット
[66 20 30 40 50 60 70 80 90 100] 小さい子と比較する
^ ^ (2*0+1) < (2*0+2)
親 子 子
[20 66 30 40 50 60 70 80 90 100] 交換して次の子と比較
^ ^ (2*1+1) < (2*1+2)
親 子 子
[20 40 30 66 50 60 70 80 90 100] 交換して次の子と比較
^ ^ (2*3+1) < (2*3+2)
親 子 子 親が小さいから終了
図 : ヒープの再構築
このアルゴリズムを Scala でプログラムすると次のようになります。
リスト : ヒープの再構築
private def downheap(n: Int)(implicit f: A => Ordered[A]): Unit = {
var c = 2 * n + 1
if (c < buff.size) {
if (c + 1 < buff.size) {
if (buff(c) > buff(c + 1)) c += 1
}
if (buff(n) > buff(c)) {
val tmp = buff(n)
buff(n) = buff(c)
buff(c) = tmp
downheap(c)
}
}
}
関数 downheap はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。最初に、n の子 c を求めます。これが buff.size よりも大きければ処理を終了します。そして、もう一つの子 (c + 1) がある場合は、小さい方の子を選択します。
次に、子 c と親 n を比較し、親が大きい場合は親と子を交換します。それから、downheap を再帰呼び出しして次の親子関係をチェックします。親が子以下の場合はヒープの条件を満たしているので処理を終了します。
最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 buff の最後尾のデータを buff の 0 番目にセットしてヒープを再構築します。上図の例でいえば、100 を buff[0] にセットして、ヒープを再構築すればいいわけです。この場合、ヒープに格納されているデータの個数は一つ減ることになります。
ところで、n 個のデータをヒープに構築する場合、n - 1 回 upheap を呼び出さなければいけません。ところが、すべてのデータを配列に格納したあと、ヒープを構築するうまい方法があります。下の図を見てください。
配列を前半と後半の 2 つに分けると、後半部分はこれより下にはデータが繋がっていない葉の部分になります。つまり、後半部分の要素は互いに関係がなく、前半部分の枝にあたる要素と関係しているだけでなのです。したがって、後半部分だけを見れば、それはヒープを満たしていると考えることができます。
あとは、前半部分の要素に対して、葉の方向に向かってヒープの関係を満たすよう修正していけば、配列全体がヒープを満たすことになります。この処理は関数 downheap を使うと次のように簡単にプログラムできます。
リスト : 列を受け取るコンストラクタ
def this(xs: Seq[A])(implicit f: A => Ordered[A]) = {
this()
buff ++= xs
for (i <- buff.size / 2 - 1 to 0 by -1) downheap(i)
}
後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。
TABLE [100 90 80 70 60|50 40 30 20 10] 後ろ半分が葉に相当
[100 90 80 70|60 50 40 30 20 10] 60 を挿入する
^
[100 90 80 70|60 50 40 30 20 10] 子供と比較する
^ ^ (2*4+1), (2*4+2)
親 子
[100 90 80 70|10 50 40 30 20 60] 交換する
・・・ 70 80 90 を順番に挿入し修正する ・・・
[100|10 40 20 60 50 80 30 70 90] 90 を挿入し修正した
[100 10 40 20 60 50 80 30 70 90] 100 を挿入、比較
^ ^ ^ (2*0+1), (2*0+2)
親 子 子
[10 100 40 20 60 50 80 30 70 90] 小さい子と交換し比較
^ ^ ^ (2*1+1), (2*1+2)
親 子 子
[10 20 40 100 60 50 80 30 70 90] 小さい子と交換し比較
^ ^ ^ (2*3+1), (2*3+2)
親 子 子
[10 20 40 30 60 50 80 100 70 90] 交換して終了
図 : ヒープの構築 (2)
それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。
なお、Scala には scala.collection.mutable に PriorityQueue というコレクションが用意されています。わざわざプライオリティキューを作る必要はないのですが、今回は Scala のお勉強ということで、あえてプログラムを作ってみましょう。
優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。最初に作成するメソッドを示します。
| メソッド | 機能 |
|---|---|
| push(x: A): Unit | データを追加する |
| pop(): A | 最小値のデータを取り出す |
| peek(): A | 最小値のデータを求める |
| isEmpty(): Boolean | キューが空ならば True を返す |
| size(): Int | ヒープの要素数を返す |
メソッド名は enqueue, dequeue としてもよかったのですが、このプログラムでは push, pop としました。なお、データを追加する関数を insert とし、最小値を取り出す関数を deleteMin とする場合もあるようです。
プログラムは次のようになります。
リスト : 優先度つき待ち行列
// 要素の追加
def push(x: A)(implicit f: A => Ordered[A]): Unit = {
buff += x
upheap(buff.size - 1)
}
// 最小値の削除
def pop()(implicit f: A => Ordered[A]): A = {
if (isEmpty()) throw new Exception("Heap is Empty")
val x = buff(0)
buff(0) = buff(buff.size - 1)
buff.dropRightInPlace(1)
downheap(0)
x
}
// 最小値の参照
def peek(): A = {
if (isEmpty()) throw new Exception("Heap is Empty")
buff(0)
}
// ヒープは空か？
def isEmpty(): Boolean = buff.size == 0
// 要素数
def size(): Int = buff.size
メソッド push は簡単です。演算子 += で buff の最後尾にデータを追加して upheap を呼び出すだけです。最後尾の添字は buff.size - 1 になります。メソッド pop はメソッド isEmpty を呼び出してヒープにデータがあるかチェックします。ヒープが空の場合はエラーを送出します。そうでなければ、buff(0) の要素を取り出して変数 x にセットします。次に、最後尾のデータ buff(buff.size - 1) を buff(0) にセットし、dropRightInPlace で末尾のデータを削除します。そして、downheap でヒープを再構築してから変数 x を返します。
あとのプログラムは簡単なので説明は割愛いたします。詳細はプログラムリストをお読みください。
それでは実際に実行してみましょう。
scala> :load heap.scala // defined class Heap scala> val a = new Heap[Int] val a: Heap[Int] = Heap@4def42c3 scala> for (i <- List(5,6,4,7,3,8,2,9,1,0)) a.push(i) scala> while (!a.isEmpty()) println(a.pop()) 0 1 2 3 4 5 6 7 8 9 scala> val b = new Heap[Int](List(9,8,7,6,5,4,3,2,1)) val b: Heap[Int] = Heap@1805ca5c scala> b.size() val res2: Int = 9 scala> b.isEmpty() val res3: Boolean = false scala> while (!b.isEmpty()) println(b.pop()) 1 2 3 4 5 6 7 8 9 scala> b.isEmpty() val res5: Boolean = true
正常に動作していますね。
最後に、Scala に用意されている PriorityQueue の使い方を簡単に説明します。
scala> import scala.collection.mutable.{PriorityQueue}
scala> val a = new PriorityQueue[Int]
val a: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue()
scala> for (i <- List(5,6,4,3,7,8,2,9,1,0)) a.enqueue(i)
scala> a.isEmpty
val res1: Boolean = false
scala> a.size
val res2: Int = 10
scala> while (!a.isEmpty) println(a.dequeue())
9
8
7
6
5
4
3
2
1
0
scala> a += 1
val res4: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue(1)
scala> a += (2,3,4,5)
there was 1 deprecation warning; re-run with -deprecation for details
1 warning found
val res5: a.type = PriorityQueue(5, 4, 2, 1, 3)
scala> a.head
val res6: Int = 5
データの追加は enqueue か演算子 +=, データの取り出しは dequeue で行います。以前のバージョンでは、+= は複数のデータをまとめて追加することができましたが、ver 2.13.0 から非推奨になりました。a ++= List(2,3,4,5) とするか、メソッド addAll を使ってください。先頭データの参照は head で行います。PriorityQueue の場合、デフォルトの設定では大きな値から順番 (降順) に取り出されることに注意してください。
データを小さい値から順番に取り出したい場合は、PriorityQueue の第 2 引数に Ordering を渡してください。この場合、メソッド reverse を使うと簡単です。Ordering[Int].reverse または Ordering.Int.reverse と指定します。
簡単な実行例を示します。
scala> val b = new PriorityQueue[Int]()(Ordering.Int.reverse) val b: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue() scala> for (i <- List(5,6,4,7,3,8,2,9,1,0)) b += i scala> while (!b.isEmpty) println(b.dequeue()) 0 1 2 3 4 5 6 7 8 9
//
// heap.scala : 配列を使ったヒープの実装
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
import scala.collection.mutable.{ArrayBuffer}
import scala.math.Ordered.orderingToOrdered
class Heap[A] {
private val buff = new ArrayBuffer[A]
// Seq を引数に受け取るコンストラクタ
def this(xs: Seq[A])(implicit f: A => Ordered[A]) = {
this()
buff ++= xs
for (i <- buff.size / 2 - 1 to 0 by -1) downheap(i)
}
// ヒープの構築
private def upheap(n: Int)(implicit f: A => Ordered[A]): Unit = {
if (n > 0) {
val p = (n - 1) / 2
if (buff(p) > buff(n)) {
val tmp = buff(p)
buff(p) = buff(n)
buff(n) = tmp
upheap(p)
}
}
}
// ヒープの再構築
private def downheap(n: Int)(implicit f: A => Ordered[A]): Unit = {
var c = 2 * n + 1
if (c < buff.size) {
if (c + 1 < buff.size) {
if (buff(c) > buff(c + 1)) c += 1
}
if (buff(n) > buff(c)) {
val tmp = buff(n)
buff(n) = buff(c)
buff(c) = tmp
downheap(c)
}
}
}
// 要素の追加
def push(x: A)(implicit f: A => Ordered[A]): Unit = {
buff += x
upheap(buff.size - 1)
}
// 最小値の削除
def pop()(implicit f: A => Ordered[A]): A = {
if (isEmpty()) throw new Exception("Heap is Empty")
val x = buff(0)
buff(0) = buff(buff.size - 1)
buff.dropRightInPlace(1)
downheap(0)
x
}
// 最小値の参照
def peek(): A = {
if (isEmpty()) throw new Exception("Heap is Empty")
buff(0)
}
// ヒープは空か？
def isEmpty(): Boolean = buff.size == 0
// 要素数
def size(): Int = buff.size
}