[ruby] ヒープソート実装

ヒープソートも書いた。

配列 a[] を下の図のように使えば、ヒープを表すことができるため、ヒープの実装には配列を使う。

子の添字を取得することも用意で、左の子は添字 * 2 + 1、右の子は添字 * 2 + 1で求めることができる。
ヒープソートの実装では使っていないけれど、親の添字は、添字 – 1 / 2

さて、ヒープソート。

class Array
  def heap_sort!
    build_heap

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

  def build_heap
    ((size-1)/2).downto(0) do |i|
      heapify(i)
    end
  end

  def heapify(index, heap_size = size)
    left  = heap_left_child_index(index)
    right = heap_right_child_index(index)

    largest = index
    largest = left  if left  < heap_size && self[left]  > self[largest]
    largest = right if right < heap_size && self[right] > self[largest]

    if largest != index
      self[largest], self[index] = self[index], self[largest]
      heapify(largest, heap_size)
    end
  end

  def heap_left_child_index(current_index)
    current_index * 2 + 1
  end

  def heap_right_child_index(current_index)
    current_index * 2 + 2
  end
end

a = [5, 22, 32, 6, 7, 81, 2, 3, 11, 6]

p a
a.heap_sort!
p a