func main()
    a = [];
    while (0 == 0)
        print("Input a size of array: ");
        n = int(scan());
        if (n <= 0)
            break;
        endif

        # Generate a random array of length n
        clear(a);
        i = 0;
        while (i < n)
            x = randrange(100000)/100.;
            append(a, x);
            i = i + 1;
        endwhile
        printArray(a);
        println("Sorting...");

        heapSort(a);

        printArray(a);
        println("----");
    endwhile
endfunc

func heapSort(ref a)
    func swap(i, j)
        nonlocal a;
        tmp = a[i]; a[i] = a[j]; a[j] = tmp;
    endfunc

    func bubbleDown(i, n)
        # i is an index of element that we sieve
        # n is a size of sub-array
        nonlocal a;
        s0 = 2*i + 1;   # Left son of a[i]
        while (s0 < n)
            s1 = s0 + 1;
            s = s0;     # Elder son
            if (s1 < n && a[s1] > a[s0])
                s = s1;
            endif
            if (a[i] >= a[s])
                return;
            endif
            swap(i, s);
            i = s;      # Go down the tree
            s0 = 2*i + 1;
        endwhile
    endfunc

    # Make a maximal binary heap
    n = len(a);
    k = n/2;
    while (k > 0)
        k = k - 1;
        bubbleDown(k, n);
    endwhile

    # Sort an array
    k = n;
    while (k > 1)
        k = k - 1;
        swap(0, k);
        bubbleDown(0, k);
    endwhile
endfunc

func printArray(ref a)
    i = 0;
    while (i < len(a))
        if (i > 0)
            # Separator
            if (i%10 == 0)
                println();
            else
                print(" ");
            endif
        endif
        print(a[i]);
        i = i + 1;
    endwhile
    println();
endfunc

main();         # Starter