• ベストアンサー

Rubyの質問です

配列を使って2分ヒープを定義したいのですが、どのように定義すればいいのでしょうか。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.1

#Wikipediaの「二分ヒープ - ヒープ操作」を参考に作ってみた。 #「upheap/downheap操作は次のような配列の点から説明できる。」以下は読んでも良く解らなかった。 #最初は配列だけにしていたが、追加操作や削除操作を持つクラスの方がわかりやすそうだったのでクラスにしました。(ループ変数の変数名がiからじゃなくてjからになっているのはその名残り) #速度や計算量の測定はしていません。 class BinaryTree def initialize @array = [] end def size @array.size end def add(val) if @array.size == 0 @array.push(val) else @array.push(val) j = @array.size - 1 while j > 0 if @array[((j - 1) / 2).floor] > @array[j] @array[j],@array[((j - 1) / 2).floor] = @array[((j - 1) / 2).floor], @array[j] else break end j = ((j - 1) / 2).floor end end val end def remove temp = @array.shift() if @array.size != 0 @array.unshift(@array.pop()) j = 0 while 2 * j + 1 < @array.size if 2 * j + 1 == @array.size - 1 minimum = 2 * j + 1 else if @array[2 * j + 1] > @array[2 * j + 2] minimum = 2 * j + 2 else minimum = 2 * j + 1 end end if @array[minimum] >= @array[j] minimum = j end @array[minimum],@array[j] = @array[j],@array[minimum] if j == minimum break else j = minimum end end end temp end def arr @array end end hoge = BinaryTree.new myarray = [12,11,13,19,15,8,7,10] while myarray.size != 0 p hoge.add(myarray.shift()) end print "---\n" p hoge.arr print "---\n" while hoge.size != 0 p hoge.remove() end

ararabre
質問者

お礼

このような大変労力のかかる作業を手伝っていただき、本当にありがとうございます。

関連するQ&A

専門家に質問してみよう