堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它通过构建最大堆（或最小堆）并反复提取堆顶元素实现排序，时间复杂度为$O(n\log n)$，且具有原地排序的特性。

算法原理

堆排序的核心分为两步： 1. 建堆：将无序数组调整为满足堆性质的完全二叉树（最大堆中父节点≥子节点，最小堆反之）。 2. 排序：反复将堆顶元素（最大值或最小值）与末尾元素交换，并重新调整堆，直到所有元素有序。

堆的性质

• 完全二叉树结构，可用数组表示。
• 对于索引$i$的节点：

 * 父节点：$\text{parent}(i)=\lfloor (i-1)/2\rfloor$  
 * 左子节点：$\text{left}(i)=2i+1$  
 * 右子节点：$\text{right}(i)=2i+2$  

graph TD A[7] --> B[3] A --> C[8] B --> D[1] B --> E[2] C --> F[5] C --> G[4]

• 图：最大堆示例（数组表示：[7,3,8,1,2,5,4]）*

算法步骤

1. 构建最大堆：从最后一个非叶子节点开始，自底向上调用`heapify`。 2. 交换与调整：

  - 将堆顶元素（最大值）与末尾元素交换。  
  - 缩小堆范围，对剩余部分重新`heapify`。  

3. 重复步骤2直到堆大小为1。

伪代码

  
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)

示例分析

输入数组: [12, 11, 13, 5, 6, 7] 1. 建堆后（最大堆）: [13, 11, 12, 5, 6, 7] 2. 第一次交换后: [12, 11, 7, 5, 6, 13] 3. 最终结果: [5, 6, 7, 11, 12, 13]

时间复杂度与空间复杂度

• 时间复杂度：

 * 建堆：$O(n)$  
 * 每次`heapify`：$O(\log n)$，共$n-1$次  
 * 总计：$O(n\log n)$  

• 空间复杂度：$O(1)$（原地排序）

实际应用

• 优先级队列：操作系统任务调度、图算法（如Dijkstra）。
• Top-K问题：只需构建大小为K的堆，无需全排序。
• 嵌入式系统：因原地排序特性，适合内存受限场景。

与其他排序算法对比

排序算法对比

算法	平均时间复杂度	空间复杂度	稳定性
堆排序	$O(n\log n)$	$O(1)$	不稳定
快速排序	$O(n\log n)$	$O(\log n)$	不稳定
归并排序	$O(n\log n)$	$O(n)$	稳定

常见问题

Q: 为什么堆排序不稳定？ A: 交换堆顶与末尾元素时，可能破坏相同键值的原始顺序（例如[3_a, 3_b, 2] → [2, 3_b, 3_a]）。

Q: 如何优化堆排序的常数因子？ A: 使用Floyd的建堆算法（自底向上`heapify`），减少比较次数。