max_heap.rb

# Use a max heap to sort an array
def heap_sort!(array) # Use ! to represent inplace
  # setup
  n = array.length
  array.unshift nil

  # build
  (n/2).downto(1) do |k|
    sink(array, k, n)
  end

  # sort
  while n > 1
    swap(array, 1, n)
    n -= 1
    sink(array, 1, n)
  end

  # teardown
  array.shift

  nil
end

def swap(array, i, j)
  t = array[i]; array[i] = array[j]; array[j] = t
end

def sink(array, k, n)
  while 2*k <= n
    j = 2*k
    j += 1 if j+1 <= n && array[j+1] > array[j]

    break if array[k] >= array[j]

    swap(array, k, j)
    k = j
  end
end

array = (1..10).to_a.shuffle
puts "array: #{array}"

heap_sort!(array)
puts "heap sort: #{array}"