Skip to content

Instantly share code, notes, and snippets.

@akht

akht/minheap.rb Secret

Created February 13, 2020 17:41
Show Gist options
  • Save akht/3749fac291c527aeb043c40b12c4950a to your computer and use it in GitHub Desktop.
Save akht/3749fac291c527aeb043c40b12c4950a to your computer and use it in GitHub Desktop.
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