13 高级排序算法之堆排序的原理与实现

在上一篇文章中，我们探讨了动态规划与数据结构结合的实例分析，了解了最优子结构的概念。今天，我们将深入研究另一种高级排序算法：堆排序。堆排序是一种基于堆的数据结构进行排序的算法，通过利用完全二叉树的性质来完成排序操作。

堆的基本概念

在深入堆排序之前，让我们先回顾一下什么是堆。堆是一种特殊的完全二叉树，每个节点值的特性如下：

• 最大堆：每个父节点的值都大于或等于其子节点的值。
• 最小堆：每个父节点的值都小于或等于其子节点的值。

在堆排序中，我们主要使用最大堆来实现升序排序。构造最大堆的过程使得堆的最大元素始终位于根节点。

堆排序的基本步骤

堆排序的过程主要可以分为两个步骤：

1. 构建最大堆：从最后一个非叶子节点开始，自下而上逐步调整，使得每个子树都满足最大堆的条件。
2. 排序操作：将根节点（最大值）与最后一个元素交换位置，然后缩小堆的存储范围（即去掉最后一个元素），再对新的根节点进行堆调整，以保持最大堆的性质。重复这个过程直到所有元素都有序。

堆排序的实现

下面我们提供一个堆排序的实现示例，使用 Python 来演示：

def heapify(arr, n, i):
    largest = i  # 初始化最大的节点为根节点
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点比根节点大
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点比当前最大的节点大
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大的不是根节点，交换它
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)  # 递归调用，堆化受影响的子树

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 一一提取元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)  # 堆化根节点
        
# 示例
arr = [3, 5, 1, 10, 2, 7]
heap_sort(arr)
print("排序后的数组:", arr)

例子分析

假设我们有一个数组 arr = [3, 5, 1, 10, 2, 7]，经过堆排序的步骤如下：

1. 构建最大堆：

   • 最初，数组的最大堆形态可能是 [10, 5, 7, 3, 2, 1]。
   • 这个过程就是通过不断调用 heapify 函数调整数组，使其符合最大堆的特性。

2. 提取元素并排序：

   • 第一步，10（最大值）与 1 交换，数组变成 [1, 5, 7, 3, 2, 10]，然后再次进行堆化。
   • 重复这个过程，最终将数组调整为 [1, 2, 3, 5, 7, 10]。

堆排序的时间复杂度

• 构建最大堆：时间复杂度为 $O(n)$。
• 排序操作：每次调整的时间复杂度为 $O(\log n)$，共需要执行 $n$ 次，所以总的时间复杂度为 $O(n \log n)$。

此外，堆排序是不稳定的排序算法，因为在排序过程中可能会改变相同元素的相对顺序。

总结

堆排序是一种高效的排序算法，尤其是在大数据集下表现优越。在本篇文章中，我们深入探讨了堆的基本原理、堆排序的步骤以及实现代码。下一篇文章中，我们将讨论另一类高级排序算法：桶排序与基数排序，它们各自的应用场景和优缺点。更多的实践将帮助我们将这些理论应用到实际问题中去，充分掌握高级排序算法的精髓。