# imperative heaps
function swap(i, j, t) {
t = x[i]
x[i] = x[j]
x[j] = t }
function siftup(n, i, p) {
i = n
while(1) {
if (i == 1) break
p = int(i / 2)
if (x[p] <= x[i]) break
swap(p, i)
i = p } }
function siftdown(n, i, c) {
i = 1
while(1) {
c = 2 * i
if (c > n) break
if (c+1 <= n)
if (x[c+1] < x[c])
c++
if (x[i] <= x[c]) break
swap(c, i)
i = c } }
function hsort(n, i) {
for (i = 2; i <= n; i++)
siftup(i)
for (i = n; i >= 2; i--) {
swap(1, i)
siftdown(i-1) } }
BEGIN {
split("4,7,8,1,5,3,2,9,6", x, ",")
hsort(9)
for (i = 1; i <= 9; i++)
print x[i] }