ヒープソート

#!/usr/bin/env ruby
 
def heep_down(data, size, root)
  while 1
    left = root * 2 + 1
    right = left + 1
    if left > size
      break
    end
    if right > size
      max = left
    else
      max = data[left] > data[right] ? left : right
    end
    if data[max] > data[root]
      data[max] = data[root] ^ data[max]
      data[root] = data[max] ^ data[root]
      data[max] = data[root] ^ data[max]
      root = max
    else
      break
    end
  end
end
 
def heap_sort(data, size)
  i = size / 2
  while i >= 0
    heep_down(data, size, i)
    i -= 1
  end
  while size > 0
    data[0] = data[size] ^ data[0]
    data[size] = data[0] ^ data[size]
    data[0] = data[size] ^ data[0]
    size -= 1
    heep_down(data, size, 0)
  end
end
 
p data = [38838, 1, 323, 43334, 112, 32]
heap_sort(data, data.size - 1)
p data