from time import clock
import sys
def parent(i):
    return i/2
def left(i):
    return 2*i
def right(i):
    return 2*i+1

def Build_Heap(a):
    global size
    length=len(a)
    compare=0
    swapp=0
    for i in range(int(length/2),0,-1):
       comparision,swap= Max_Heapify(a,i,length)
       compare=compare+comparision
       swapp=swapp+swap
    size=size+sys.getsizeof(length)+sys.getsizeof(compare)+sys.getsizeof(swapp)+sys.getsizeof(a)
    return compare,swapp

def Max_Heapify(a,i,length):
    global size
    l=left(i)
    r=right(i)
    comparision=0
    swap=0
    if l<=length and a[l-1]>a[i-1]:
        comparision=comparision+2
        largest=l
    else:
        largest=i
    if r<=length and a[r-1]>a[largest-1]:
        comparision=comparision+2
        largest=r
    if largest!=i:
        swap=swap+1
        a[largest-1],a[i-1]=a[i-1],a[largest-1]
        Max_Heapify(a,largest,length)
    size=size+sys.getsizeof(a)+sys.getsizeof(swap)+sys.getsizeof(largest)+sys.getsizeof(i)+sys.getsizeof(length)+sys.getsizeof(l)+sys.getsizeof(r)
    return comparision,swap

def Heapsort(a):
    global size
    comparision,swap=Build_Heap(a)
    length=len(a)
    for i in range(len(a),1,-1):
        a[0],a[i-1]=a[i-1],a[0]
        swap=swap+1
        length=length-1
        compr,swa=Max_Heapify(a,1,length)
        comparision=comparision+compr
        swap=swap+swa
    size=size+sys.getsizeof(comparision)+sys.getsizeof(swap)+sys.getsizeof(length)+sys.getsizeof(i)
    return comparision,swap

try:      
    input=open('in10_10.txt','r+')
    output=open('out_33_10_10_1.txt','w+')
except IOError:
    print "The file does not exist"
list=[]
list1=[]
list2=[]
size=0
for row in input.readlines():
    list=row.split(",")
    for i in range(len(list)):
        if list[i]=="\n":
            pass
        else:
            list1.append(int(list[i]))
size=size+sys.getsizeof(list)+sys.getsizeof(list1)
start=clock()
comparision,swap=Heapsort(list1)
time=clock()-start
for i in list1:
    output.write(str(i)+", ")
output.write("\nNo. Of Comarisions Are: "+str(comparision)+"\nNo. of Swaps Are: "+str(swap))
output.write("\nTime Consumed is: "+str(time)+" Secs")
output.write("\nMemory Used is: "+str(size)+" Bytes")
input.close()
output.close()