（二叉）堆基础 二叉堆是一个数组，它可以被看成一个近似的完全二叉树。树的节点始终从左向右填充，因此除了最底层外，该树是完全充满的。 二叉堆可分为最大堆和最小堆。最大堆满足某个节点的值必须大于或等于其子节点的值；最小堆则相反。 调整堆 调整堆意在维护最大堆或最小堆的性质。以最大堆为例，其节点的值都要满足小于或等于其父节点的值。因此，堆中的最大元素存放在根节点中，并且，在任一子树种，该子树所包含的所有节点的值都不大于该子树根节点的值。 调整堆的思路是对于节点 i，我们假设以其子节点为根节点的子树都是最大堆，但这时 i 节点的值可能小于其孩子，由此需要通过调整将其下降到正确的位置上去，在下降的过程中，根节点始终与子节点中较大的且大于它本身的节点交换。 如有一数组：[27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]，如下图所示：以红色节点“3”为例，该节点明显不满足最大堆的要求，因此将其“下降”，先与其子节点”10“交换，再进一步与”9“交换，得到调整后的数组：[27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0]。 下面是用 Python 编写的调整堆函数 max_heapify()： def max_heapify(l, i, end=None): """ 调整堆 :param l: 堆列表 :param i: 要调整的根节点的下标 :return: 无返回 """ end = end or len(l) # 找到其左孩子和右孩子 left = 2 * i + 1 right = 2 * i + 2 top_value = l[i] try: left_value = l[left] except IndexError: # 堆是从左至右填充的，因此如果其左孩子没有值，则结束调整 return try: right_value = l[right] except IndexError: right_value = None # 找到最大的值及其位置 max_pos, max_value = i, top_value for pos, value in zip([left, right], [left_value, right_value]): if pos < end and value and value > max_value: max_pos, max_value = pos, value if not i == max_pos: # 交换，使 i 的值在最大堆中“逐级下降” l[i], l[max_pos] = l[max_pos], l[i] # 递归调用，，从而使得以下标 i 为根节点的子树重新遵循最大堆的性质 max_heapify(l, max_pos, end) 构建堆 回归之前调整堆的方法，对于节点 i，始终假设以该子节点为根节点的子树都是最大堆。因此在构建堆时，必须时刻满足该假设，因此可以用自底而上的方法来构建一个最大堆。由此可编写出 build_max_heap() 函数： import math def build_max_heap(l): """ 建最大堆 :param l: 堆列表 :return: 无返回 """ # 自底向上的利用 max_heaplify 将列表转换为最大堆 # 只用取 math.floor(len(l) / 2.0) 之前的进行调整，之后的均为树的叶节点 pos = list(range(math.floor(len(l) / 2.0))) pos.reverse() for i in pos: max_heapify(l, i) 堆排序 我们已经知道如何构建一个最大堆，也就是说根节点就是数组的最大值。因此可以将其取出，然后再维护剩余的堆至最大堆，再次取出根节点，由此重复直到堆中仅有一个元素，则可得到一个排序好的数组。在得到最大堆后，我们可以始终将根节点与最后一个节点的值进行交换，然后将堆缩小一位，以实现原址排序。而维护剩余节点，仅仅是新的根节点可能打破了最大堆的性质，因此只需要对新的根节点进行一次调整即再一次满足了最大堆的性质。根据此思路，可以得到 heap_sort() 函数： def heap_sort(l): """ 堆排序 :param l: 堆列表 :return: 无返回 """ # 先构建一个最大堆 build_max_heap(l) pos = list(range(1, len(l))) pos.reverse() for i in pos: # 列表中的最大元素总在根节点A[1]中，通过把它与A[n]进行互换，可以让该元素放到正确的位置 l[0], l[i] = l[i], l[0] # 然后从堆中去掉节点 n，在剩余的节点中，原来根的孩子节点仍然是最大堆，而新的根节点可能会违背最大堆的心智， # 因此调用 max_heapify(l, 0) 重新构造一个最大堆 max_heapify(l, 0, i) 让我们来观察一次运行过程（在执行前，我在每一次循环中打印了列表的状态）： >>> from heapsort import * >>> l = [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0] >>> heap_sort(l) 14 -> [27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0] 13 -> [17, 16, 10, 7, 13, 9, 1, 5, 0, 12, 4, 8, 3, 27] 12 -> [16, 13, 10, 7, 12, 9, 1, 5, 0, 3, 4, 8, 17, 27] 11 -> [13, 12, 10, 7, 8, 9, 1, 5, 0, 3, 4, 16, 17, 27] 10 -> [12, 8, 10, 7, 4, 9, 1, 5, 0, 3, 13, 16, 17, 27] 9 -> [10, 8, 9, 7, 4, 3, 1, 5, 0, 12, 13, 16, 17, 27] 8 -> [9, 8, 3, 7, 4, 0, 1, 5, 10, 12, 13, 16, 17, 27] 7 -> [8, 7, 3, 5, 4, 0, 1, 9, 10, 12, 13, 16, 17, 27] 6 -> [7, 5, 3, 1, 4, 0, 8, 9, 10, 12, 13, 16, 17, 27] 5 -> [5, 4, 3, 1, 0, 7, 8, 9, 10, 12, 13, 16, 17, 27] 4 -> [4, 1, 3, 0, 5, 7, 8, 9, 10, 12, 13, 16, 17, 27] 3 -> [3, 1, 0, 4, 5, 7, 8, 9, 10, 12, 13, 16, 17, 27] 2 -> [1, 0, 3, 4, 5, 7, 8, 9, 10, 12, 13, 16, 17, 27] 1 -> [0, 1, 3, 4, 5, 7, 8, 9, 10, 12, 13, 16, 17, 27] 时间复杂度 调整堆的过程，其时间复杂度为O(lgn)； 构建堆的过程，其时间复杂度为O(n)； 堆排序，其时间复杂度为O(nlgn)。 参考文档 《算法导论》第六章