import random

#heap sort
#Rafal Gawlik
#www.algorytm.org

#sortowanie stogowe
def heap_sort(L):
	"""Sortowanie Heap sort"""

	#budowanie kopca
	print("[LOG] Budowanie kopca")
	for start in range(int((len(L)-2)/2), -1, -1):
		shiftdown(L, start, len(L)-1)

	#sortowanie
	for end in range(len(L)-1, 0, -1):
		print("[LOG] Zamiana: "+str(L[end])+" z "+str(L[0]))
		L[end], L[0] = L[0], L[end] #swap
		shiftdown(L, 0, end - 1) #przywracanie wlasnosci kopca
	return L
 
#spusc element pod indeksem start w dol - tak by byl zachowany warunek kopca
def shiftdown(lst, start, end):
	"""Metoda do produkcji kopca"""
	root = start
	print("[LOG] Przywracanie wlasnosci kopca")
	print("[LOG] Ustalamy korzen: "+str(root))
	while True:
		child = root * 2 + 1
		if child > end: break
		if child + 1 <= end and lst[child] < lst[child + 1]:
			child += 1
		if lst[root] < lst[child]:
			lst[root], lst[child] = lst[child], lst[root]
			root = child
		else:
			break

#generuj zbior danych wejsciowych w porzadku malejacym
def malejaco(n):
	L = []
	for i in range(0,n):
		L.append(n-i-1)
	return L

#generuj zbior danych wejsciowych w porzadku losowym
def losowe(n):
	L = []
	a = range(0,n)
	for i in range(0,n):
		L.append(random.choice(a))
	return L


#przyklad uzycia
n = input('Podaj ilosc danych: ')
w = input('Dane wejsciowe: Losowo/Malejaco [1/2]: ')

if int(w) == 1:
	L = losowe(int(n))
	print(L)
elif int(w) == 2:
	L = malejaco(int(n))
	print(L)
else:
	print('napisales bzdure')

L = heap_sort(L)

print('Po posortowaniu:')
print(L)