import time
import sys
t1=time.clock()
compare=0
swap=0

def max_heapsort(lst,size):
  for n in range(0,size):
      for start in range((len(lst)-2)/2, -1, -1):
          siftdown(lst, start, len(lst)-1)
 
      for end in range(len(lst)-1, 0, -1):
          lst[end], lst[0] = lst[0], lst[end]
          siftdown(lst, 0, end - 1)
  return lst
 
def siftdown(lst, start, end):
  global compare
  global swap
  root = start
  while True:
    child = root * 2 + 1
    if child > end:
        compare=compare+1
        break
    if child + 1 <= end and lst[child] < lst[child + 1]:
      child += 1
      compare=compare+1
    if lst[root] < lst[child]:
      lst[root], lst[child] = lst[child], lst[root]
      root = child
      compare=compare+1
      swap=swap+1
    else:
      break


f1 = file('in10_10.txt')
l=f1.readlines()

five_sets=[]

numbers1=l[1].split()
set1=[]
for i in range(0,len(numbers1)-1):
    a=int(numbers1[i][0:len(numbers1[i])-1])
    set1.append(a)
set1.append(int(numbers1[len(numbers1)-1]))
five_sets.append(set1)

numbers2=l[3].split()
set2=[]
for i in range(0,len(numbers2)-1):
    a=int(numbers2[i][0:len(numbers2[i])-1])
    set2.append(a)
set2.append(int(numbers2[len(numbers2)-1]))
five_sets.append(set2)

numbers3=l[5].split()
set3=[]
for i in range(0,len(numbers3)-1):
    a=int(numbers3[i][0:len(numbers3[i])-1])
    set3.append(a)
set3.append(int(numbers3[len(numbers3)-1]))
five_sets.append(set3)

numbers4=l[7].split()
set4=[]
for i in range(0,len(numbers4)-1):
    a=int(numbers4[i][0:len(numbers4[i])-1])
    set4.append(a)
set4.append(int(numbers4[len(numbers4)-1]))
five_sets.append(set4)

numbers5=l[9].split()
set5=[]
for i in range(0,len(numbers5)-1):
    a=int(numbers5[i][0:len(numbers5[i])-1])
    set5.append(a)
set5.append(int(numbers5[len(numbers5)-1]))
five_sets.append(set5)

f2=open('out_20_10_10a.txt', 'w')
for i in range(0,len(five_sets)):
  f2.write(str(max_heapsort(five_sets[i],len(five_sets[i])))+'\n')
f2.write('\n'+'total no of comparisons is '+str(compare)+'\n')
f2.write('total no of swappings is'+str(swap)+'\n')
var_list=[t1,l,numbers1,numbers2,numbers3,numbers4,numbers5,set1,set2,set3,set4,set5,five_sets,i,a]
psize=0
for i in range(0, len(var_list)):
 psize = psize +sys.getsizeof(var_list[i])
t2=time.clock()
psize =psize +sys.getsizeof(t2)+sys.getsizeof(psize)
f2.write('memory used is '+" "+str(psize)+' bytes'+'\n')
f2.write('\ntime taken is '+" "+str(t2-t1)+' seconds'+ '\n')
f2.close()