ヒープの操作

配列で表現された2分ヒープに対しての操作
完全2分木は配列で表現できる

def deleteMin_heap(arr)
  arr[0] = arr.pop # 最後尾をrootへ
  sift_down(arr, 0)
end

# i番目の要素を適切な位置まで下げていく
def sift_down(arr, i)
  leftIdx = 2 * i + 1
  rightIdx = 2 * i + 2

  # 左の子が存在しないなら終了
  return arr if arr[leftIdx].nil?

  # cIdx:左右の子で小さい方のidx、右の子がなければ左の子
  cIdx = if  arr[rightIdx].nil? || (arr[leftIdx] < arr[rightIdx])
           leftIdx
         else
           rightIdx
         end

  # 子のほうが大きいなら終了
  return arr if arr[i] < arr[cIdx]

  arr[cIdx], arr[i] = arr[i], arr[cIdx]
  sift_down(arr, cIdx)
end

def insert_heap(arr, d)
  arr.push(d)
  sift_up(arr, arr.length - 1)
end

# i番目の要素を適切な位置まで上げていく
def sift_up(arr, i)
  pIdx = (i - 1) / 2
  return arr if i == 0 # rootなら終了
  return arr if arr[i] > arr[pIdx] # 子のほうが大きいなら終了

  arr[i], arr[pIdx] = arr[pIdx], arr[i]
  sift_up(arr, pIdx)
end