堆排序

定义与基本思想

堆排序（Heap Sort）是一种利用堆这种数据结构设计的高效排序算法。其基本思想是：将序列构建成大顶堆（或小顶堆），每次取堆顶元素放到序列末尾，调整剩余元素为新堆，重复直到全部有序。

堆排序演示

105341

当前堆顶: 10

下一步

算法描述

1. 将待排序序列建成大顶堆
2. 取出堆顶元素（最大值），与末尾元素交换，堆长度减 1
3. 调整剩余元素为新大顶堆
4. 重复步骤 2-3，直到堆长度为 1

伪代码如下：

function heapSort(A, n):
    buildMaxHeap(A, n)
    for i = n-1 downto 1:
        swap(A[0], A[i])
        heapify(A, 0, i)

function buildMaxHeap(A, n):
    for i = n/2-1 downto 0:
        heapify(A, i, n)

function heapify(A, i, n):
    largest = i
    l = 2*i+1
    r = 2*i+2
    if l < n and A[l] > A[largest]:
        largest = l
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        swap(A[i], A[largest])
        heapify(A, largest, n)

时间复杂度分析

• 最好/最坏/平均情况：$O(n\log n)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定排序

练习题

练习 1

对数组 $A = [4, 10, 3, 5, 1]$ 进行堆排序，写出初始建堆和第一次交换后的堆结构。

参考答案

解题思路：先建大顶堆，再交换堆顶和末尾。

详细步骤：

1. 初始建堆：[10, 5, 3, 4, 1]
2. 第一次交换：[1, 5, 3, 4, 10]，再调整为新堆：[5, 4, 3, 1, 10]

答案：如上，第一次交换后最大元素归位。

练习 2

堆排序的时间复杂度和空间复杂度分别是多少？

参考答案

解题思路：考查复杂度和空间。

详细步骤：

1. 时间复杂度 $O(n\log n)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n\log n)$，空间 $O(1)$。