Rubyでバイナリ・ヒープを書いてみた
各ノードの子が常に親より大きくなる（あるいは小さくなる）バイナリ・ヒープを作ってみた。ヒープはソートに使われるほかにも、順序付きキュー（pre-ordered queue）など結構重要な応用があるらしい。
順序のあるキューを配列で実現する場合、3つのアプローチがある。
1. キューに入れるときに挿入ソートのようなことをして、常に配列の中身をソート済みにする。取り出しは端から順に
2. キューの配列は未ソート。取り出すときに最小なり最大を選択して取り出す。取り出し時に配列のスライドが必要
3. ヒープを使う
1は取り出しがO(1)で高速だし、2は入れるほうがO(1)だけど、その逆の操作ではそれぞれO(n)の計算量が必要になる。一方、ヒープを使えば出し入れともO(log n)で済む。
珠玉のプログラミングに丁寧な解説とC++のコード例あった。なるほどなと、すんなり分かったつもりで本を閉じてRubyで書き始めけど、やっぱり一発では動かなかった。siftupまでは動いたけど、siftdownが動かなかった。トップに置いたノードをsiftdownで下に落としていくときの場合分けは、抽象的なタンゴの入れ替えの「操作イメージ」としては自明だけど、ステップバイステップの「処理」としては、そこまで自明ということはない。で、紙に簡単な図を書いて、それを見ながらやると、劇的にコーディングが楽になることを発見した。
class MyHeap def initialize(size) @max = size + 1 # we don't use q[0] for practical reasons @q = Array.new(@max, 0) # heap / pre-ordered queue @n = 0 # number of items end def insert(i) if @n + 1 > @max then puts "full" return end @n += 1 @q[@n] = i siftup(@n) end def extract if @n == 0 then puts "empty" return end min = @q[1] @q[1] = @q[@n]; @q[@n] = 0 @n -= 1 siftdown(1) min end def siftup(n) while n > 1 if @q[n] < @q[n / 2] then @q[n], @q[n / 2] = @q[n / 2], @q[n] n = n / 2 else return end end end def siftdown(n) if n * 2 > @n then return elsif n * 2 == @n then if @q[n] > @q[n * 2] then @q[n], @q[n * 2] = @q[n * 2], @q[n] end elsif n * 2 + 1 <= @n then left = n * 2 right = n * 2 + 1 if (@q[left] < @q[right]) && (@q[n] > @q[left]) then @q[n], @q[left] = @q[left], @q[n] siftdown(left) end if (@q[right] < @q[left]) && (@q[n] > @q[right]) then @q[n], @q[right] = @q[right], @q[n] siftdown(right) end end end def to_s n = 1 while n < @n str = "" (n..n*2-1).each do |i| gap = (6 - Math::log(n,2)).to_i if gap <= 0 then gap = 1 end str += "#{@q[i]}"+" "*gap end print " "*((80 - str.size) / 2) ,"#{str}\n" n = n * 2 end end end if __FILE__ == $0 then h = MyHeap.new(20) a = []; 30.times{a << rand(30)}; a.uniq! # => [8, 9, 6, 18, 23, 19, 27, 11, 26, 16, 21, 17, 14, 29, 5, 15] a.each{|x|h.insert(x)} while true puts h gets print "extracted: #{h.extract}\n" end end
MyHeap#to_sが汚いし出力もイマイチだけど、結果はこんな感じ。
% irb
>> require "heap.rb"
=> true
>> h = MyHeap.new(20)
=> #<MyHeap:0x8377474 @max=21, @q=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], @n=0>
>> a = []; 30.times{a << rand(30)}; a.uniq!
=> [26, 17, 25, 15, 5, 12, 28, 11, 21, 7, 8, 0, 27, 20, 3, 16, 13, 29, 2, 6]
>> a.each{|x|h.insert(x)}
=> [26, 17, 25, 15, 5, 12, 28, 11, 21, 7, 8, 0, 27, 20, 3, 16, 13, 29, 2, 6]
>> h
=> #<MyHeap:0x8377474 @max=21, @q=[0, 0, 2, 3, 7, 6, 12, 5, 15, 13, 8, 11, 25, 27, 28, 20, 26, 16, 29, 21, 17], @n=20>
>> h.to_s
0
2 3
7 6 12 5
15 13 8 11 25 27 28 20
26 16 29 21 17
=> nil
>> 表示は見にくいけど、ちゃんとヒープになっている。
% ruby heap.rb
0
1 7
3 25 14 13
8 5 27 28 22 17 20 18
11 29 10 0 0
#<MyHeap:0x8265e00>
extracted: 0
1
3 7
5 25 14 13
8 10 27 28 22 17 20 18
11 29 0 0 0
#<MyHeap:0x8265e00>
extracted: 1
3
5 7
8 25 14 13
11 10 27 28 22 17 20 18
#<MyHeap:0x8265e00>
extracted: 3
5
8 7
10 25 14 13
11 29 27 28 22 17 20 18
#<MyHeap:0x8265e00>
extracted: 5
7
8 13
10 25 14 18
11 29 27 28 22 17 20 0
#<MyHeap:0x8265e00>
extracted: 7
8
10 13
11 25 14 18
20 29 27 28 22 17 0 0
#<MyHeap:0x8265e00>
extracted: 8
10
11 13
17 25 14 18
20 29 27 28 22 0 0 0
#<MyHeap:0x8265e00>
extracted: 10
11
17 13
20 25 14 18
22 29 27 28 0 0 0 0
#<MyHeap:0x8265e00>
extracted: 11
13
17 14
20 25 28 18
22 29 27 0 0 0 0 0
#<MyHeap:0x8265e00>
extracted: 13
14
17 18
20 25 28 27
22 29 0 0 0 0 0 0
#<MyHeap:0x8265e00>
extracted: 14
17
20 18
22 25 28 27
#<MyHeap:0x8265e00>
extracted: 17
18
20 27
22 25 28 29
#<MyHeap:0x8265e00>うまく動いてるように見えるけど、最後の方、to_sがバグってるっぽい。to_sはヒープとは直接関係ないけど。
21
22 25
26 24 0 0
#<MyHeap:0x8265e00>
extracted: 21
22
24 25
#<MyHeap:0x8265e00>
extracted: 22
24
26 25
#<MyHeap:0x8265e00>
extracted: 24
25
#<MyHeap:0x8265e00>
extracted: 25
#<MyHeap:0x8265e00>
extracted: 26
#<MyHeap:0x8265e00>
empty
extracted:
#<MyHeap:0x8265e00>
