#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
from random import *

# move an element down the tree until it is in the right place
def heapdown(h, k, end) :
    v = h[k]
    while 2*k<end :
        # go to children
        j = 2*k         

        # if two children set j to bigger of two
        if j+1<end :
             if h[j] < h[j+1] :
                j = j+1

        # if heap property is satisfied we are done
        if v>= h[j] :
            break
        else :
            h[k] = h[j]
            k = j
    h[k] = v
    return k

# remove the maximum element from the heap AND put it at the end
def popmax(h, end) :
    max = h[1]     # we don't use h[0] because of numbering
    h[1] = h[end-1]
    heapdown(h, 1, end-1)
    return max

# heap is numbered from 1 to n with location 0 ignored
def makeheap(h) :
    for i in range(len(h)//2, 0, -1) :
        heapdown(h, i, len(h))
    return h

def heapsort(h) :
    makeheap(h)
    print(h)
    for i in range(len(h)-1, 1, -1) :
        h[i] = popmax(h, i+1)
        print(h)
    return h

def main() :
    seed(33331)
    x = [-1]
    for i in range(1, 100) :
        x.append(int(uniform(0, 1000)))
    print(x)
    return(heapsort(x))


main()