当前位置：首页 > article >正文

堆的常见应用1

article 2025/3/31 0:38:01

堆排序

堆排序就是利用堆的思想来对数据进行排序，其实主要就分为两个步骤，即建堆和堆的删除。

概念解惑

在正式介绍如何排序之前，先理清一些基本的操作，如什么时候用向上调整，什么时候用向下调整，以及分别在什么操作下对应什么位置来进行这些调整。

在堆排序中，构建大顶堆时确实使用向下调整（Heapify Down），但需要明确调整的起始点和调整方向的区别。

1. 向下调整（Heapify Down）的本质

调整方向：从某个节点向下与其子节点比较，确保父节点 ≥ 子节点（最大堆）。
起始点：构建堆时，从最后一个非叶子节点开始，自底向上遍历所有非叶子节点。
- 为什么是最后一个非叶子节点？
  完全二叉树中，最后一个非叶子节点的下标为 n/2 - 1（n 是数组长度）。这些节点是“潜在不满足堆性质”的最小单元，调整它们可以高效构建堆。
- 处理顺序：从最后一个非叶子节点（最底层）向根节点方向逐个处理。

以这个二叉树为例子：

最后一个非叶子节点是值为 2 的节点（下标 2）。
调整顺序：先处理 2，再处理 5，最后处理根节点 3。

2. 向上调整（Heapify Up）的本质

调整方向：从某个节点（通常是新插入的叶子节点）向上与其父节点比较，确保子节点 ≤ 父节点（最大堆）。
起始点：插入新元素时，从新插入的叶子节点开始，逐步向上调整到根。
- 适用场景：适合动态插入元素到已有堆中（如优先队列）。
- 时间复杂度：每次插入需 O(log n) 时间，构建堆需 O(n log n)。

3. 代码对比：构建堆的两种方式

方式1：向下调整（正确且高效）

void buildMaxHeap(int arr[], int n) {
// 从最后一个非叶子节点开始，逆序处理所有非叶子节点
for (int i = n/2 - 1; i >= 0; i--) {
heapifyDown(arr, n, i); // 对每个非叶子节点向下调整
}
}

//时间复杂度：O(n)

方式2：向上调整（低效，仅用于插入）

void buildMaxHeapWrong(int arr[], int n) {
// 错误示范：逐个插入元素，从叶子节点向上调整
for (int i = 0; i < n; i++) {
heapifyUp(arr, i); // 对每个新插入的节点向上调整
}
}

//时间复杂度：O(n log n)（效率低，不推荐用于构建堆）

4.直观总结

这张图可以很好地概括这些问题：

5. 为什么构建堆不用向上调整？

数学证明：向下调整的时间复杂度为 O(n)，而向上调整需要 O(n log n)。
直观理解：叶子节点占总数的一半，调整叶子节点无意义（它们没有子节点）。向下调整从非叶子节点开始，减少了冗余操作。

堆排序原理

堆排序是一种高效的排序算法，利用二叉堆（通常为最大堆）数据结构实现。其核心思想是通过构建堆结构，反复提取最大元素并调整剩余部分，最终得到有序序列。

构建堆：将无序数组调整为最大堆（父节点值 ≥ 子节点值）（升序：建大堆，降序：建小堆）
排序阶段：
- 交换堆顶（最大值）与当前末尾元素。
- 缩小堆范围，重新调整剩余元素为最大堆。
- 重复上述步骤，直到所有元素有序。

简要实现（升序）

向下调整方法（递归版）

#include <stdio.h>

// 交换元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整以i为根的子树为最大堆
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);          // 调整剩余部分为堆
    }
}

堆排序的适用场景

优点
- 时间复杂度稳定，始终为 O(nlog⁡n)。
- 空间复杂度为O（1），适合内存有限的环境。

构建堆阶段：O(n)

排序阶段：O(n log n)

总时间复杂度：O(n) + O(n log n) = O(n log n)

无论是平均还是最坏情况，排序阶段的 O(n log n) 主导总时间复杂度，因此堆排序的时间复杂度稳定为 O(n log n)。

堆排序的时间复杂度与输入数据的初始顺序无关：

构建堆阶段：无论数据是否有序，都需要遍历所有非叶子节点调整。

排序阶段：每次提取堆顶后，必须从根节点向下调整，调整次数固定为树的高度（log n）。

因此，最坏情况与平均情况时间复杂度一致，均为 O(n log n)。