【アルゴリズムの勉強】Rubyでヒープソートを書いてみる

アルゴリズムの勉強としてRubyでヒープソートを実装する。

ヒープソートとは

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。
アルゴリズムは、以下のように2つの段階から構成される。
未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
計算量は O {\displaystyle (n\log n)} (n\log n) となる[2]。安定ソートではない[2]。

ヒープソート - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count

def make_heap(arr, parent, end_element)
  temp = arr[parent]
  child = 0

  while parent < (end_element + 1) / 2
    left_child = (parent * 2) + 1
    right_child = left_child + 1

    if right_child <= end_element && arr[right_child] > arr[left_child]
      child = right_child
    else
      child = left_child
    end

    if temp >= arr[child]
      break
    end

    arr[parent] = arr[child]
    parent = child
  end

  arr[parent] = temp
end

def heap_sort(arr, number_of_elements)
  center = (number_of_elements - 1) / 2
  while center >= 0
    make_heap(arr, center, number_of_elements - 1)
    center += -1
  end

  end_element = number_of_elements - 1
  while end_element > 0
    arr[0], arr[end_element] = arr[end_element], arr[0]
    make_heap(arr, 0, end_element - 1)
    end_element += -1
  end
end

heap_sort(arr, number_of_elements)
p arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献、参考リンク

• 明解 Javaによるアルゴリズムとデータ構造