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

# properties of a heap
# for all k: h[k] >= h[2*k] and h[k] >= h[2*k+1]
# tree is filled in from lowest to highest index without gaps
#
# derived properties: 
#   1. for a given set of numbers there are many legal heaps
#   2. a monotonically decreasing list of numbers is a heap
#   3. a heap is not necessarily a monotonically decreasing set of numbers

def isheap(h) :
    for i in range(1, len(h)) :
        if 2*i<len(h) and h[2*i]>h[i] :
            return False
        if 2*i<len(h) and h[2*i+1]>h[i] :
            return False
    return True

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

        print("d")
        # if two children set j to bigger of two
        if j+1<len(h) :
             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

# move an element up the tree until it is in the right place
def heapup(h, k) :
    v = h[k]
    while k>1 :
        print("u")
        if h[k//2]<v :
            h[k] = h[k//2]
            k = k//2
        else :
            break
    h[k] = v
    return k


# add to a heap by putting element at the end then heapup
def addheap(h, v) :
    h.append(v)
    heapup(h, len(h)-1)

    return h

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

# remove any element from the heap
def rmheap(h, i) :
    v = h[i]
    h[i] = h[len(h)-1]
    if h[i]>v :
        heapup(h,i)
    else :
        heapdown(h, i)

    return h

# 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)
    return h

def makeheap2(h) :
    for i in range(1, len(h)) :
        heapup(h, i)
    return h

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

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

def main2() :
    x = [-1]
    for i in range(1, 8) :
        x.append(i)
    print(x)
    print(makeheap(x))
    print(isheap(x))
    x = [-1]
    for i in range(1, 8) :
        x.append(i)
    print(x)
    print(makeheap2(x))
    print(isheap(x))

main()