算法05-堆排序

堆排序详解

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它的核心思想是利用堆的性质（最大堆或最小堆）来实现排序。堆排序分为两个主要步骤：建堆和排序。

---

1. 什么是堆？

堆是一种特殊的完全二叉树，分为两种：

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

在堆排序中，通常使用最大堆。

---

2. 堆排序的步骤

步骤1：建堆

• 将待排序的数组看作一个完全二叉树。
• 从最后一个非叶子节点开始，逐步调整每个子树，使其满足最大堆的性质。
• 调整的过程称为堆化（Heapify）：
  • 比较当前节点与其左右子节点，找到最大值。
  • 如果最大值不是当前节点，则交换它们的位置。
  • 继续向下调整，直到子树满足最大堆的性质。

步骤2：排序

• 将堆顶元素（最大值）与数组的最后一个元素交换，此时最大值已经放到正确的位置。
• 排除最后一个元素，对剩余的堆重新进行堆化，使其再次满足最大堆的性质。
• 重复上述过程，直到堆中只剩下一个元素。

---

3. 堆排序的特点

时间复杂度

• 建堆：( O(n) )
• 排序：每次堆化需要 ( O(\log n) )，总共需要 ( n-1 ) 次堆化，因此排序的时间复杂度为 ( O(n \log n) )。
• 总时间复杂度：( O(n \log n) )

空间复杂度

• 堆排序是原地排序算法，不需要额外的存储空间，空间复杂度为 ( O(1) )。

稳定性

• 堆排序是不稳定的排序算法，因为在交换堆顶元素和最后一个元素时，可能会改变相同元素的相对顺序。

---

4. 堆排序的优缺点

优点

• 时间复杂度稳定，最坏情况下也是 ( O(n \log n) )。
• 不需要额外的存储空间，适合内存受限的环境。

缺点

• 不稳定排序，可能改变相同元素的相对顺序。
• 在实际应用中，由于频繁的交换操作，堆排序的常数因子较大，性能可能不如快速排序或归并排序。

---

5. 堆排序的应用场景

• 适合需要排序大规模数据的场景，尤其是对内存使用有严格限制的环境。
• 常用于实现优先队列。

---

总结

• 堆排序是一种高效的排序算法，通过构建最大堆并逐步提取最大值来实现排序。虽然它的时间复杂度较好，但由于其不稳定性和较大的常数因子，在实际应用中需要根据具体需求选择是否使用。
• 堆排序通过建堆和排序两个步骤，逐步将最大值放到数组末尾，最终实现排序。它的时间复杂度为O(nlogn)，是一种高效的排序算法。

堆排序详解（结合例子和图形）

我们通过一个具体的例子和图形来讲解堆排序的过程。

例子

假设我们有一个待排序的数组：
[4, 10, 3, 5, 1]
我们的目标是将这个数组按升序排列。

步骤1：建堆

将数组看作一个完全二叉树：

        4/ \10  3/ \5   1

目标：

将这个二叉树调整为最大堆（每个节点的值都大于或等于其子节点的值）。

调整过程

• (1) 从最后一个非叶子节点开始（节点 10）。

• (2) 比较节点 10 和其子节点 5 和 1，发现 10 已经是最大值，无需调整。

• (3) 调整节点 4：

  • 比较节点 4 和其子节点 10 和 3，发现 10 是最大值。

  • 交换 4 和 10。

  • 调整后的树：

        10/ \4    3/ \
    5   1
    

• (4) 继续调整节点 4：

  • 比较节点 4 和其子节点 5 和 1，发现 5 是最大值。

  • 交换 4 和 5。

  • 调整后的树：

        10/ \5    3/ \
    4   1
    

现在，树已经是一个最大堆。

---

步骤2：排序

目标：将堆顶元素（最大值）放到数组末尾，并逐步缩小堆的范围。

排序过程

• (1) 将堆顶元素 10 与最后一个元素 1 交换：

  [1, 5, 3, 4, 10]

  树结构：

        1/ \5    3/4
  

• (2) 排除最后一个元素 10，对剩余部分重新堆化：

  • 调整节点 1：

    • 比较节点 1 和其子节点 5 和 3，发现 5 是最大值。

    • 交换 1 和 5。

    • 调整后的树：

          5/ \1    3/
      4
      

  • 继续调整节点 1：

    • 比较节点 1 和其子节点 4，发现 4 是最大值。

    • 交换 1 和 4。

    • 调整后的树：

          5/ \4    3/
      1
      

• (3) 将堆顶元素 5 与最后一个元素 1 交换：
  [1, 4, 3, 5, 10]

  树结构：

        1/ \4    3
  

• (4) 排除最后一个元素 5，对剩余部分重新堆化：

  • 调整节点 1：

    • 比较节点 1 和其子节点 4 和 3，发现 4 是最大值。

    • 交换 1 和 4。

    • 调整后的树：

      4/ \
    1    3
    

• (5) 将堆顶元素 4 与最后一个元素 3 交换：

[3, 1, 4, 5, 10]

树结构：

      3/1

• (6) 排除最后一个元素 4，对剩余部分重新堆化：

  • 调整节点 3：

  • 比较节点 3 和其子节点 1，发现 3 已经是最大值。

  • 无需调整。

• (7) 将堆顶元素 3 与最后一个元素 1 交换：
  [1, 3, 4, 5, 10]

最终结果

数组已经按升序排列：
[1, 3, 4, 5, 10]

图形总结

• (1) 初始数组：

  [4, 10, 3, 5, 1]

• (2) 建堆后：

  [10, 5, 3, 4, 1]

• (3) 排序过程：

  每次将堆顶元素放到数组末尾，并重新堆化。

• (4) 最终结果：

[1, 3, 4, 5, 10]

示例代码

def heapify(arr, n, i):"""堆化函数：调整以 i 为根的子树，使其满足最大堆的性质。:param arr: 待排序的数组:param n: 堆的大小:param 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):"""堆排序函数:param arr: 待排序的数组"""n = len(arr)# 步骤1：建堆# 从最后一个非叶子节点开始，逐步调整for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 步骤2：排序# 将堆顶元素（最大值）与数组末尾元素交换，并重新堆化for i in range(n - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]  # 将最大值放到数组末尾heapify(arr, i, 0)  # 重新堆化剩余部分# 示例
arr = [4, 10, 3, 5, 1]
print("排序前:", arr)
heap_sort(arr)
print("排序后:", arr)

© 著作权归作者所有