当前位置：首页 > news >正文

算法05-堆排序

news 2025/6/22 13:10:33

堆排序详解

堆排序（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)