堆排序算法详解

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法，具有时间复杂度稳定、不需要额外存储空间等优点。以下是堆排序的详细解析：

一、堆的基本概念

堆的定义
堆是一种特殊的完全二叉树，分为大顶堆和小顶堆：
- 大顶堆：每个节点的值都大于或等于其子节点的值（根节点）。
- 小顶堆：每个节点的值都小于或等于其子节点的值（根节点最小）。
堆的存储方式
堆通常用数组存储，父子节点的索引关系为：
- 父节点索引：i
- 左子节点索引：2i + 1
- 右子节点索引：2i + 2

二、堆排序的核心步骤

堆排序分为两个阶段：建堆和排序。

1. 建堆（Heapify）

目标：将无序数组调整为堆结构（通常是大顶堆）。
方法：从最后一个非叶子节点开始，向上调整堆。
时间复杂度：O(n)
（通过自底向上的调整，避免重复比较）

调整堆的伪代码（以大顶堆为例）：
```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)

```

2. 排序

目标：将堆顶元素（值）与末尾元素交换，缩小堆范围，重复调整堆。
步骤：
1. 将堆顶元素与最后一个元素交换。
2. 缩小堆范围（排除最后一个元素）。
3. 调整剩余堆结构。
时间复杂度：O(n log n)
（每次调整堆的时间复杂度为 O(log n)，共需调整 n 次）

排序的伪代码：
```python
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[0], arr[i] = arr[i], arr[0]  # 交换堆顶和末尾元素
    heapify(arr, i, 0)  # 调整剩余堆

```

三、堆排序的完整示例

以数组 [4, 10, 3, 5, 1] 为例：

建堆（大顶堆）：
- 初始数组：[4, 10, 3, 5, 1]
- 调整过程：
  - 从索引 1 开始调整，最终得到堆：[10, 5, 3, 4, 1]
排序：
- 次交换：[1, 5, 3, 4, 10]，调整堆：[5, 4, 3, 1, 10]
- 第二次交换：[1, 4, 3, 5, 10]，调整堆：[4, 1, 3, 5, 10]
- 第三次交换：[1, 3, 4, 5, 10]，调整堆：[3, 1, 4, 5, 10]
- 第四次交换：[1, 3, 4, 5, 10]，调整堆：[3, 1, 4, 5, 10]（已排序）

最终结果：[1, 3, 4, 5, 10]

四、堆排序的优缺点

| 优点 | 缺点 |
|-------------------------|-------------------------|
| 时间复杂度稳定（O(n log n)） | 不稳定排序（交换可能改变相同元素的相对顺序） |
| 原地排序（空间复杂度 O(1)） | 相较于快速排序，实际运行速度较慢 |

五、堆排序的应用场景

优先队列：堆是优先队列的底层实现。
流式数据排序：适合处理动态数据（如实时日志排序）。
内存受限环境：由于空间复杂度低，适合嵌入式系统。

六、代码实现（Python）

```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[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)