ヒープソート

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書) | 大槻 兼資, 秋葉 拓哉 |本 | 通販 | Amazon

この本を読んでいて、ヒープソートの実装が割とスッと入ってきたので、メモを残しておく。

ヒープの条件

• 頂点vの親頂点をpとしたとき、key[p]>=key[v]が成立する。
• 木の高さをhとしたとき、木の深さh-1以下の部分については、完全二分木を形成している。
• 木の高さをhとした時、木の深さhの部分については、頂点が左詰めされている。

引用：問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書) | 大槻 兼資, 秋葉 拓哉 |本 | 通販 | Amazon

実装(ruby)

class Array
  def heapify!(i, n)
    child1 = i * 2 + 1
    return if child1 >= n

    child1 += 1 if child1 + 1 < n && self[child1 + 1] > self[child1]
    return if self[child1] <= self[i]

    self[i], self[child1] = self[child1], self[i]
    heapify!(child1, n)
  end

  def heap_sort!()
    n = self.size
    (n / 2 - 1).downto(0) do |i|
      heapify!(i, n)
    end

    (n - 1).downto(1) do |i|
      self[0], self[i] = self[i], self[0]
      heapify!(0, i)
    end
  end
end

a = [12, 9, 15, 3, 8, 17, 6, 1]
a.heap_sort!
p a