-
-
Save akht/3749fac291c527aeb043c40b12c4950a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class MinHeap | |
def initialize(source) | |
@arr = [] | |
source.each do |e| | |
push(e) | |
end | |
end | |
def size | |
@arr.size | |
end | |
def empty? | |
@arr.empty? | |
end | |
# ヒープの最小値を返す(削除しない) | |
def top | |
@arr.first | |
end | |
# ヒープに値を追加する | |
def push(value) | |
@arr << value # 最後尾に追加 | |
i = @arr.size - 1 # 追加されたノード番号 | |
# 親子関係を修復していく | |
while i > 0 | |
parent = (i - 1) / 2 # 親のノード番号 | |
# 親子関係が逆転してなかったら終了 | |
break if @arr[parent] <= value | |
# 親と自分をswap | |
@arr[parent], @arr[i] = @arr[i], @arr[parent] | |
i = parent | |
end | |
# 追加したい値は最終的にこの位置に決定する | |
@arr[i] = value | |
end | |
# ヒープから最小値を取り出す | |
def pop | |
min = top # 最小値 = 返り値 | |
# ここからヒープを再構築する | |
# ひとまず最後尾をルートノードにもっていくる | |
tmp_node = @arr.last | |
@arr.pop | |
# ルートノードから降ろしていく | |
i = 0 | |
while (i * 2 + 1) < size | |
# 左側の子が配列のサイズを超えるまで | |
# = 左側の子が配列サイズを超えているということは、 | |
# そのノードには子が存在しないということになる | |
# 左右の子ノードの値を比較して小さい方をmin_childとする | |
lhs_child = i * 2 + 1 # 左側の子 | |
rhs_child = i * 2 + 2 # 右側の子 | |
min_child = lhs_child # とりあえず左側が小さいと仮定しておく(右側の子が存在しないこともあるため) | |
if rhs_child < size | |
# 右側の子のインデックスが配列のサイズを超えていないとき | |
# = 超えているということは、右側の子は存在しないということ | |
# => その場合は左側の子が採用される | |
if @arr[lhs_child] > @arr[rhs_child] | |
min_child = rhs_child | |
end | |
end | |
# 逆転していなければ終了 | |
break if @arr[min_child] >= tmp_node | |
# 自分のノードを子の値にする | |
@arr[i] = @arr[min_child] | |
i = min_child | |
end | |
# 選んだノードは最終的にこの位置に決定(空なら最後の要素だったということなのでセット不要) | |
@arr[i] = tmp_node unless empty? | |
min | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment