堆的简介

堆（Heap）是一种特殊的树形数据结构，满足以下性质：

  1. 它是一个完全二叉树。
    • 即每一层从左到右完全填满，除了最后一层的节点可以不满，但必须从左到右排列。
  2. 堆的性质：
    • 每个节点的值总是满足一定的顺序关系：
      • 最大堆（Max Heap）：每个节点的值都大于等于其子节点的值。
      • 最小堆（Min Heap）：每个节点的值都小于等于其子节点的值。

堆常用于实现优先队列以及高效的排序算法（如堆排序）。

堆的分类

  1. 最大堆（Max Heap）：

    • 根节点是整个堆中最大的元素。
    • 子节点的值总小于或等于父节点的值。
    • 应用：优先队列中的最大优先级。

    示例：

    1
    2
    3
    4
    5
         50
        /  \
      30    20
     / \    /
    15 10  8

  2. 最小堆（Min Heap）：

    • 根节点是整个堆中最小的元素。
    • 子节点的值总大于或等于父节点的值。
    • 应用：优先队列中的最小优先级。

    示例：

    1
    2
    3
    4
    5
        5
       / \
      10  15
     / \
    20 30

堆的操作

1. 插入

  • 过程：

    1. 将新元素插入堆的最后一层，保持完全二叉树的性质。
    2. 调整堆（上浮操作）：
      • 比较新元素与其父节点的值，若违反堆的性质，交换位置。
      • 重复此过程，直到堆的性质恢复。

  • 时间复杂度：( O(\log n) )（树的高度）。

2. 删除

  • 删除堆顶元素（最大堆的最大值或最小堆的最小值）。

  • 过程：

    1. 将堆的最后一个元素移动到堆顶，删除原堆顶元素。
    2. 调整堆（下沉操作）：
      • 比较新堆顶与其子节点的值，若违反堆的性质，交换位置。
      • 重复此过程，直到堆的性质恢复。

  • 时间复杂度：( O(\log n) )。

3. 堆化

  • **堆化（Heapify）**是将一个无序数组调整为堆的过程。

  • 过程：

    • 从最后一个非叶子节点开始向上调整子树，确保每个子树都满足堆的性质。
    • 最终整个树成为一个堆。

  • 时间复杂度：( O(n) )（对每个节点调整的代价逐层减少）。

4. 堆排序

堆排序是一种基于堆的数据排序算法。

  • 过程：

    1. 将数组构建为一个最大堆。
    2. 取出堆顶元素（最大值）放到数组末尾，并将剩余元素重新调整为最大堆。
    3. 重复此过程，直到所有元素排序完成。

  • 时间复杂度：( O(n \log n) )。

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

堆的实现

堆通常用数组来实现，因其结构是完全二叉树，可以通过数组索引轻松定位节点关系：

  • 对于数组中的索引 ( i )：
    • 父节点：( \text{parent}(i) = \lfloor (i-1)/2 \rfloor )
    • 左子节点：( \text{left}(i) = 2i + 1 )
    • 右子节点：( \text{right}(i) = 2i + 2 )

示例（最大堆）：
数组表示：[50, 30, 20, 15, 10, 8]
对应的树：

1
2
3
4
5
     50
    /  \
  30    20
 / \    /
15 10  8

堆的应用场景

  1. 优先队列：

    • 堆常用于实现优先队列，能够高效获取和删除优先级最高的元素。

  2. 排序算法：

    • 堆排序利用堆的特性，实现高效的排序。

  3. 图算法：

    • 最短路径算法（如Dijkstra）和最小生成树算法（如Prim）需要用堆来维护优先队列。

  4. 操作系统：

    • 堆数据结构用于处理任务调度、内存分配等。

  5. 实时数据流：

    • 用堆维护动态数据的Top K问题，如查找动态数据流中的最大或最小值。

总结

  • 堆是一种完全二叉树，分为最大堆和最小堆。
  • 它支持高效的插入、删除和优先级操作，广泛应用于优先队列、排序和图算法等领域。

堆排序的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
using namespace std;

// 调整堆，使以 root 为根的子树满足最大堆性质
void heapify(vector<int>& arr, int n, int root) {
    int largest = root;            // 假设根节点是最大的
    int left = 2 * root + 1;       // 左子节点索引
    int right = 2 * root + 2;      // 右子节点索引

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

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

    // 如果最大值不是根节点
    if (largest != root) {
        swap(arr[root], arr[largest]); // 交换根节点和最大节点
        heapify(arr, n, largest);     // 递归调整子树
    }
}

// 堆排序算法
void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 1. 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 提取元素并调整堆
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素移到末尾
        swap(arr[0], arr[i]);

        // 调整剩余部分为最大堆
        heapify(arr, i, 0);
    }
}

// 主函数
int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};

    cout << "原数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    heapSort(arr);

    cout << "排序后数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

代码解析

  1. heapify函数：

    • 将以 root 为根的子树调整为最大堆。
    • 递归地保证子树满足堆的性质。

  2. 构建最大堆：

    • 从最后一个非叶子节点开始（n/2 - 1），逐层向上调整堆。
    • 时间复杂度为 ( O(n) )。

  3. 排序过程：

    • 每次将堆顶（最大值）与末尾元素交换。
    • 减少堆的有效范围，并对剩余部分重新调整为最大堆。
    • 每次调整的时间复杂度为 ( O(\log n) )，总共 ( n ) 次操作，因此排序复杂度为 ( O(n \log n) )。

运行示例

输入数组：

1
12, 11, 13, 5, 6, 7

排序过程：

  1. 构建最大堆：
1
2
3
4
5
     13
    /  \
  12    7
 / \    /
5  6   11
  1. 提取最大值：
1
2
3
4
5
6
交换 13 和 7，然后调整剩余部分：
        12
       /  \
     11    7
    / \
   5   6
  1. 重复，直到排序完成：
    输出：
1
5, 6, 7, 11, 12, 13

特点

  • 时间复杂度：( O(n \log n) )。
  • 空间复杂度：( O(1) )（原地排序）。
  • 适用场景：需要稳定性能、不依赖额外存储的排序任务。