一、堆排序简介

1. 理论

如果给定输入列表 A[1..n] ，其中 n=len(A) ，则 堆排序 算法需要先构建一个最大堆，即最大元素总是位于根节点处，且所有子节点不大于其父节点。由于最大元素位于根节点 A[1] 处，因此我们可以通过如下步骤对A进行排序：

首先，将根节点和 A[n] 进行交换，则最大值的位置确定；
其次，由于新的根节点可能使得当前完全二叉树违背堆序性质，因此可以采用元素交换的方式使其重新满足堆序性质，需要注意的是，此时元素交换时无需再考虑元素 A[n] ；
然后，将新的根节点和 A[n-1] 进行交换，则次大值的位置确定；
再次，由于新的根节点可能使得当前完全二叉树违背堆序性质，再次采用元素交换的方式使其重新满足堆序性质，需要注意的是，此时元素交换时无需再考虑元素 A[n] 和 A[n-1] ；
最后，重复上述过程，直到 A[1..n] 按照非递减顺序排列。

2. 图解

2.1 建最大堆

实际上，给定一个列表，建一个最大堆的流程和建一个最小堆的流程基本一致，具体地，针对给定的10个元素列表，建堆步骤如下：

首先，同建最小堆一样，如图 $(a)$ 所示，自底向上，先确保以位置5为根节点的完全二叉树是一个二叉堆，此时满足最大堆的堆序性质，不涉及元素交换；
其次，确保以位置4为根节点的完全二叉树是一个二叉堆，此时违背了最大堆的堆序性质，需对位置4和位置8的元素进行交换，如结果如图 $(c)$ 所示；
紧接着，依次确保以位置3，2，1处为根节点的完全二叉树是一个二叉堆，最终建堆结果如图 $(f)$ 所示。

在这里插入图片描述

2.2 用最大堆排序

下面是利用上述创建的最大堆进行排序的过程，具体地：

首先，将根节点元素16和最底层最右侧元素1交换，然后通过元素交换使得不包括16在内的其他节点均满足堆序性质，结果如图 $(b)$ 所示；
然后，将根节点元素14和最底层最右侧元素1交换，然后通过元素交换使得不包括16和14在内的其他节点均满足堆序性质，结果如图 $(c)$ 所示；
重复上述过程，直到所有元素排好序，如图 $(j)$ 所示。

在这里插入图片描述

二、堆排序实现

由于堆一定是一个二叉树，而二叉树的实现可以是基于链式结构，也可以基于数组结构，为降低实现难度，且避免使用链式结构导致额外的内存开销（如一个节点保存其父、子节点引用所需的变量），这里使用基于数组结构来描述二叉树。

def __down_heap(arr, num, j):
    """
    通过元素交换，确保列表arr[0:num]中，元素arr[j]及其子孙节点满足堆序性质
    :param arr: 列表形式给出的待排序列
    :param num: 列表索引上限
    :param j: 列表元素的索引
    :return: None
    """
    left = 2 * j + 1  # 元素arr[j]左子节点的索引
    right = 2 * j + 2  # 元素arr[j]右子节点的索引
    if left < num:  # 判断arr[j]是否有左子节点
        large_child = left
        if right < num:  # 判断arr[j]是否有右子节点
            if arr[right] > arr[left]:
                large_child = right
        if arr[large_child] > arr[j]:  # 确保最终建成最大堆
            arr[large_child], arr[j] = arr[j], arr[large_child]  # 交换两个节点处的值使满足堆序性质
            __down_heap(arr, num, large_child)


def heapify(arr):
    """将列表形式给出的元素视为完全二叉树，对其进行建堆"""
    for j in range((len(arr) - 1) // 2, -1, -1):  # 建堆
        __down_heap(arr, len(arr), j)


def heap_sort(arr):
    """堆排序"""
    heapify(arr)  # 构建最大堆
    # 依次将最大值，次大值...最小值从右往左排好
    for i in range(len(arr) - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 每一次迭代，将当前堆中最大元素排好序
        __down_heap(arr, i, 0)  # 每迭代一次后元素arr[i]已排好序，仅需确保前i个元素满足堆序性质


if __name__ == '__main__':
    arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    heap_sort(arr)
    print(arr)

三、堆排序复杂度

1. 时间复杂度

堆排序的时间复杂度分为两个部分：

一部分是调用 heapify 函数的建最大堆所需的时间开销，由之前的理论分析可知为 $O (n)$ ；
另一部分是循环调用 __down_heap 方法确保未排序的完全二叉树为最大堆的时间开销，可按照如下计算：

$log(n-1)+log(n-2)+\cdot\cdot\cdot+log(1)=log((n-1)!)$

而：

$l o g ((n - 1)!) < l o g (n!) < n l o g (n)$

最后忽略低阶项 $O (n)$ ，故最坏时间复杂度为 $n l o g (n)$ 。

2. 空间复杂度

由上述堆排序的实现代码可以看出，在堆排序过程中，除了输入的待排序列和排序过程中使用的辅助变量外，没有额外的内存开销，因此这是典型的原地排序，故其最坏空间复杂度为 $\Theta{(n)}$ 。

【常见算法Python描述】堆排序简介及实现

文章目录