Rubyの質問です

質問

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

回答No.1

himajin100000 · ベストアンサー

#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

お礼

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