ヒープソートをやってみる。

• 常に子よりも親が大きい（小さい）値の二分木をヒープという。

今度はヒープを使ったソート、ヒープソートをやってみます。

def heap(array,n)
  if n > 0
    parent = (n - 1) / 2 # 親の位置
    if array[n] > array[parent]
      tmp = array[n]
      array[n] = array[parent]
      array[parent] = tmp
    end
    heap(array,parent)
  end
end

def out(array,sorted)
  (array.size-1).downto(1) do |n|
    heap(array,n)
  end
  sorted.push(array.shift)
  array.unshift(array.pop)
  array.size > 1 ? out(array,sorted) : sorted.push(array.shift)
end

array  = []
sorted = []

10.times do
 array.push(rand(100))
end

p array  #=> [51, 34, 77, 16, 46, 37, 94, 38, 36, 75]
out(array,sorted)
p sorted #=> [94, 77, 75, 51, 46, 38, 37, 36, 34, 16]