堆排序的原理是什么？

推荐答案

堆排序是一种基于二叉堆数据结构的比较排序算法。它的核心思想是通过构建一个最大堆（或最小堆），将堆顶元素（即最大值或最小值）与堆的最后一个元素交换，然后调整剩余元素使其重新满足堆的性质，重复这一过程直到所有元素有序。

堆排序的时间复杂度为 O(n log n)，其中 n 是待排序元素的数量。它是一种原地排序算法，不需要额外的存储空间。

本题详细解读

1. 堆的基本概念

堆是一种特殊的完全二叉树，分为最大堆和最小堆：

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

在堆排序中，通常使用最大堆来进行升序排序。

2. 堆排序的步骤

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

2.1 建堆

建堆的过程是将一个无序的数组调整为一个最大堆。具体步骤如下：

1. 从最后一个非叶子节点开始，向前遍历每个节点。
2. 对于每个节点，执行“下沉”操作，即将当前节点与其子节点比较，如果子节点的值更大，则交换它们的位置，并继续向下调整，直到当前节点大于其子节点或到达叶子节点。

2.2 排序

排序的过程是将堆顶元素（最大值）与堆的最后一个元素交换，然后将剩余元素重新调整为最大堆。具体步骤如下：

1. 将堆顶元素与堆的最后一个元素交换，此时最大值已经位于数组的末尾。
2. 将堆的大小减一，忽略已经排序好的元素。
3. 对新的堆顶元素执行“下沉”操作，重新调整堆。
4. 重复上述步骤，直到堆的大小为1，排序完成。

3. 堆排序的代码实现（Python示例）

// www.javascriptcn.com code example
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[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)  # 调整剩余堆

# 示例
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组:", arr)

4. 堆排序的时间复杂度分析

• 建堆：O(n)
• 排序：O(n log n)
• 总时间复杂度：O(n log n)

堆排序是一种高效的排序算法，尤其适用于需要原地排序的场景。