N = 10000000

def pushDown(h, pos, n)
  while 2 * pos + 1 < n
    j = 2 * pos + 1
    if j + 1 < n && h[j + 1] > h[j]
      j += 1
    end
    if h[pos] >= h[j]
      break
    end
    h[pos], h[j] = h[j], h[pos]
    pos = j
  end
end

def main
  start = Time.now

  h = Array.new(N) { |i| i }

  (N / 2).downto(0) do |i|
    pushDown(h, i, N)
  end

  n = N
  while n > 1
    h[0], h[n - 1] = h[n - 1], h[0]
    n -= 1
    pushDown(h, 0, n)
  end

  N.times do |i|
    if h[i] != i
      raise 'h[i] != i'
    end
  end

  print("Done in #{((Time.now - start) * 1000).to_i}\n")
end

main