def build_max_heap(to_build_list):
  """建立一個堆"""
  # 自底向上建堆
  for i in range(len(to_build_list)/2 - 1, -1, -1):
    max_heap(to_build_list, len(to_build_list), i)
def max_heap(to_adjust_list, heap_size, index):
  """調(diào)整列表中的元素以保證以index為根的堆是一個最大堆"""
  # 將當(dāng)前結(jié)點與其左右子節(jié)點比較，將較大的結(jié)點與當(dāng)前結(jié)點交換，然后遞歸地調(diào)整子樹
  left_child = 2 * index + 1
  right_child = left_child + 1
  if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]:
    largest = left_child
  else:
    largest = index
  if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]:
    largest = right_child
  if largest != index:
    to_adjust_list[index], to_adjust_list[largest] = \
    to_adjust_list[largest], to_adjust_list[index]
    max_heap(to_adjust_list, heap_size, largest)
def heap_sort(to_sort_list):
  """堆排序"""
  # 先將列表調(diào)整為堆
  build_max_heap(to_sort_list)
  heap_size = len(to_sort_list)
  # 調(diào)整后列表的第一個元素就是這個列表中最大的元素，將其與最后一個元素交換，然后將剩余的列表再調(diào)整為最大堆
  for i in range(len(to_sort_list) - 1, 0, -1):
    to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
    heap_size -= 1
    max_heap(to_sort_list, heap_size, 0)
if __name__ == '__main__':
  to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
  heap_sort(to_sort_list)
  print to_sort_list