#!/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