def build_heap(arr) (arr.length / 2 - 1).downto(0) do |i| sift_down(arr, i) end arr end def heap_sort(arr) build_heap(arr) result =[] (arr.length - 1).downto(0) do |i| arr[0], arr[i] = arr[i], arr[0] result.push(arr.pop) sift_down(arr, 0) …

配列で表現された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 …