from collections import deque


def swap_param(L, i, j):
 # 堆顶与最后元素交换
 L[i], L[j] = L[j], L[i]
 return L

def heap_adjust(L, start, end):
 #构造成大根堆
 temp = L[start]
 i = start
 j = 2 * i
 while j <= end:
 # 判断左右子节点，取两个子节点最大索引
 if (j < end) and (L[j] < L[j + 1]):
  j += 1
 # 判断根节点与子节点比较，如果子节点大于根节点，子节点赋值给根节点
 if temp < L[j]:
  L[i] = L[j]
  i = j
  j = 2 * i
 else:
  break
 # 再把 原来根节点值赋值给子节点上
 L[i] = temp

def heap_sort(L):
 L_length = len(L) - 1

 first_sort_count = L_length // 2
 for i in range(first_sort_count):
 heap_adjust(L, first_sort_count - i, L_length)

 for i in range(L_length - 1):
 L = swap_param(L, 1, L_length - i)
 heap_adjust(L, 1, L_length - i - 1)

 return [L[i] for i in range(1, len(L))]

def main():
 L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
 L.appendleft(0)
 print(heap_sort(L))

main()