堆排序怎么排过程图解？初始堆的建立方法是什么？

1.1 堆的定义

堆是一种特殊的完全二叉树，具有以下性质：

最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。堆顶（根节点）为最大值。
最小堆（Min Heap）：strong>每个节点的值都小于或等于其子节点的值。堆顶（根节点）为最小值。

1.2 完全二叉树

完全二叉树是一种特殊的二叉树，除了最后一层外，每一层的节点数都达到最大值，且最后一层的节点都集中在左侧。

1.3 堆的存储方式

堆通常使用数组来表示。对于数组中的元素，假设索引从0开始：

父节点索引：parent(i) = (i – 1) / 2
左子节点索引：left(i) = 2 * i + 1
右子节点索引：right(i) = 2 * i + 2

2. 堆排序的工作原理

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

建立初始堆：将无序数组转化为堆结构（最大堆）。
排序过程：将堆顶元素（最大值）与堆的最后一个元素交换，缩小堆的大小，并重新调整堆以维持堆的性质。重复此过程，直到堆的大小为1。

2.1 初始堆的建立

初始堆的建立过程称为**堆化（Heapify）**。从最后一个非叶子节点开始，向上逐步调整每个节点以满足堆的性质。

找到最后一个非叶子节点的位置。
从最后一个非叶子节点开始，向上对每个节点执行堆化操作。
直到根节点被堆化，整个数组转化为堆。

**公式：**

最后一个非叶子节点的索引 = n/2 - 1 （n为节点总数，整数除法）

2.2 堆的调整（堆化）

堆化是指将一个部分满足堆性质的树调整为完全满足堆性质的树。

选择当前节点与其子节点中的较大者进行比较。
如果当前节点小于较大的子节点，则交换两者的位置。
递归地对被交换的子节点执行堆化操作。

2.3 排序过程

排序过程包括以下步骤：

将堆顶元素（最大值）与堆的最后一个元素交换。
缩小堆的大小（忽略最后一个元素）。
对新的堆顶执行堆化操作，恢复堆的性质。
重复上述步骤，直到堆的大小为1。

3. 堆排序的过程图解

以下通过一个具体示例，结合过程图解，帮助理解堆排序的工作过程。

3.1 初始数组

假设我们有一个无序数组：

[4, 10, 3, 5, 1]

3.2 建立初始堆

**步骤1：找到最后一个非叶子节点**

数组长度 n = 5
最后一个非叶子节点索引 = n/2 – 1 = 1

**步骤2：从索引1开始堆化**

当前节点值：10
左子节点索引：3，值为5
右子节点索引：4，值为1
10已经大于其子节点，无需调整。

**步骤3：堆化索引0**

当前节点值：4
左子节点索引：1，值为10
右子节点索引：2，值为3
较大子节点为10，交换4和10。
交换后数组：[10, 4, 3, 5, 1]
对交换后的子节点索引1进行堆化：
- 当前节点值：4
- 左子节点索引：3，值为5
- 右子节点索引：4，值为1
- 较大子节点为5，交换4和5。
- 最终堆化后的数组：[10, 5, 3, 4, 1]

3.3 排序步骤

步骤1：交换堆顶与最后一个元素
- 交换10与1。
- 交换后数组：[1, 5, 3, 4, 10]
- 缩小堆的大小至4。
- 对堆顶1进行堆化：
  - 当前节点值：1
  - 左子节点索引：1，值为5
  - 右子节点索引：2，值为3
  - 较大子节点为5，交换1和5。
  - 交换后数组：[5, 1, 3, 4, 10]
  - 对交换后的子节点索引1进行堆化：
    - 当前节点值：1
    - 左子节点索引：3，值为4
    - 右子节点索引：4，已超出当前堆大小
    - 较大子节点为4，交换1和4。
    - 最终堆化后的数组：[5, 4, 3, 1, 10]
步骤2：再次交换堆顶与最后一个元素
- 交换5与1。
- 交换后数组：[1, 4, 3, 5, 10]
- 缩小堆的大小至3。
- 对堆顶1进行堆化：
  - 当前节点值：1
  - 左子节点索引：1，值为4
  - 较大子节点为4，交换1和4。
  - 交换后数组：[4, 1, 3, 5, 10]
  - 对交换后的子节点索引1进行堆化：
    - 当前节点值：1
    - 左子节点索引：3，已超出当前堆大小
    - 无需进一步调整。
步骤3：再次交换堆顶与最后一个元素
- 交换4与3。
- 交换后数组：[3, 1, 4, 5, 10]
- 缩小堆的大小至2。
- 对堆顶3进行堆化：
  - 当前节点值：3
  - 左子节点索引：1，值为1
  - 较大子节点为3，无需交换。
步骤4：最后一次交换堆顶与最后一个元素
- 交换3与1。
- 交换后数组：[1, 3, 4, 5, 10]
- 缩小堆的大小至1。
- 排序完成。

最终排序结果：

[1, 3, 4, 5, 10]

4. 堆排序的优缺点

4.1 优点

时间复杂度稳定：堆排序的时间复杂度始终为O(n log n)，不受数据初始排列影响。
空间复杂度低：堆排序是一种原地排序算法，空间复杂度为O(1)。
无需递归：可以通过迭代方式实现，避免递归带来的栈空间消耗。

4.2 缺点

不稳定：堆排序不是一种稳定的排序算法，因为在堆化和交换过程中，可能会改变相等元素的相对顺序。
常数因子较高：相比快速排序，堆排序的实际性能可能略逊一筹，尤其是在数据量较小时。
缺乏局部性：堆排序的内存访问模式较为随机，可能导致缓存命中率较低。

5. 堆排序的实现示例

5.1 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[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)

# 示例使用
if __name__ == "__main__":
    arr = [4, 10, 3, 5, 1]
    print("原始数组:", arr)
    heap_sort(arr)
    print("排序后数组:", arr)

输出：

原始数组: [4, 10, 3, 5, 1]
排序后数组: [1, 3, 4, 5, 10]

5.2 C语言实现

#include <stdio.h>

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 堆化过程
void heapify(int arr[], int n, int i) {
    int largest = i;       // 初始化最大值为根节点
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点存在且大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i) {
        swap(&arr[i], &arr[largest]);

        // 递归堆化受影响的子树
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 -1; i >=0; i--)
        heapify(arr, n, i);

    // 一个个取出元素
    for (int i = n-1; i >0; i--) {
        // 移动当前根到末尾
        swap(&arr[0], &arr[i]);

        // 调整剩余的堆
        heapify(arr, i, 0);
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i=0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("n");
}

// 示例使用
int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    heapSort(arr, n);

    printf("排序后数组: ");
    printArray(arr, n);
}