def sift(li, low, high): ‘‘‘ :param li:树 :param low: 树的根节点 :param high: 树的最后一个节点 :return:向下调整树 ‘‘‘ tmp = li[low] # 去除树根作为临时变量 i = low # i指向空位 j = 2 * i + 1 # 第一次 j指向根节点的左孩子 while j <= high: # 循环继续的条件：j不越界；This the second end condition：j越界 # 1.比较左右子节点 if j + 1 <= high and li[j] < li[j + 1]: # 右节点存在，才进行左右比较 j += 1 # 将j指向j+1 if li[j] > tmp: # 调整位置 li[i] = li[j] # 空位的元素填成j下标的元素，所谓的调整 i = j # 向下调整 j = 2 * j + 1 # 从当前j节点找左孩子 else: break # j位置的元素>tmp 停止循环，This the first end condition li[i] = tmp # 结束循环，空位填充tmp #堆排 def heak_sort(li): n = len(li) # 1.构造堆 for low in range((n - 2) // 2, -1, -1): # 根据子节点找父节点i-->(i-1)//2 sift(li, low, n - 1) print(li) # 2.挨个出数 for high in range(n - 1, -1, -1): li[0], li[high] = li[high], li[0] sift(li, 0, high - 1) # 排除堆中的最后一个元素 li = [8, 1, 2, 6, 3, 7] heak_sort(li) print(li) # [1, 2, 3, 6, 7, 8]
原文：https://www.cnblogs.com/liuer-mihou/p/12659785.html