Rubyの質問です

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

No.1 ベストアンサー 回答者： himajin100000 回答日時： 2009/01/14 14:48

#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

この回答へのお礼

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

お礼日時：2009/01/15 17:44