#/***********************************************************
#    heapsort.rb -- ヒープソート
#***********************************************************/

def heapsort(n,  a)
    (n / 2).downto(1) do |k|
        i = k;  x = a[i]
        while ((j = 2 * i) <= n) 
            if (j < n && a[j] < a[j + 1]); j += 1; end
            if (x >= a[j]); break; end
            a[i] = a[j];  i = j
        end
        a[i] = x
    end
    while (n > 1) 
        x = a[n];  a[n] = a[1];  n -= 1
        i = 1
        while ((j = 2 * i) <= n) 
            if (j < n && a[j] < a[j + 1]); j += 1; end
            if (x >= a[j]); break; end
            a[i] = a[j];  i = j
        end
        a[i] = x
    end
end

N = 20
a = []

printf("Before:")
for i in 1..N
    a[i] = (rand * 100 + 1).to_i
    printf(" %2d", a[i])
end
printf("\n")

heapsort(N, a)

printf("After: ")
for i in 1..N; printf(" %2d", a[i]); end
printf("\n")

exit 0