[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/GNupGt4H    [ raw code | fork ]

programmingpraxis - Plain Text, pasted on Jan 25:
# 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] }


Create a new paste based on this one


Comments: