目录
  1. 1. 堆的定义
  2. 2. 基本操作
    1. 2.1. 向下调整
    2. 2.2. 向上调整
    3. 2.3. 建堆
    4. 2.4. 删除堆顶
    5. 2.5. 插入
  3. 3. 应用

堆的定义

堆(Heap) 是通常是一个可以被看作 完全二叉树数组 对象。总是满足以下性质:

  • 堆中某个结点的值总是不大于或不小于其父结点的值

    • 不大于:大根堆;不小于:小根堆
  • 堆总是一棵完全二叉树

    • 具有 n 个结点,深度为 log2k+1\lfloor log_2k \rfloor + 1

    • 根据结点编号可以得出父结点、左右孩子

堆虽然是数组对象,但是它是非线性数据结构,相当于一维数组,有两个直接后继。对于任意结点 i[1,n]i \in[1, n]

  • 若 i = 1,则结点 i 是二叉树的根,无双亲;若 i >= 1,则双亲是 i/2
  • 若 2i > n,则无左孩子,否则左孩子是 2i
  • 若 2i + 1 > n,则无右孩子,否则右孩子是 2i + 1
1
2
const int maxn = 100;
int heap[maxn], n = 10;

i 也可以是 0 基的,则对应的双亲、左右孩子变为:(i - 1)/2、2i + 1、2i + 2

基本操作

堆的基本操作有:调整成堆(向下、向上)、建堆、插入、删除。下面以大根堆为例。

向下调整

总是将当前结点 V 与它的左右孩子进行比较,假如存在比 V 大的孩子,则将最大的孩子与 V 进行交换;交换完毕后,继续让结点 V 与孩子比较,直至 V 比它的孩子都大或者没有孩子了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void downAdjust(int low, int high) {
int i = low, j = low * 2;
while (j <= high) {
if (j + 1 <= high && heap[j + 1] > heap[j]) {
j = j + 1;
}
if (heap[j] > heap[i]) {
swap(heap[j], heap[i]);
i = j;
j = 2 * i;
} else {
break;
}
}
}
  • 时间复杂度:O(logn)O(logn)

向上调整

从最下面的叶子结点开始往上调整:

1
2
3
4
5
6
7
8
9
10
11
12
void upAdjust(int low, int high) {
int i = high, j = high / 2;
while (j >= low) {
if (heap[j] < heap[i]) {
swap(heap[j], heap[i]);
i = j;
j = i / 2;
} else {
break;
}
}
}
  • 时间复杂度:O(logn)O(logn)

建堆

建堆的过程一般采用的向下调整的方式。假设有 n 个元素,由于完全二叉树的叶子结点为 n/2\lceil n/2 \rceil,因此下标从在 [1,n/2][1, \lfloor n/2 \rfloor] 的都是非叶子结点,因此可以从 n/2\lfloor n/2 \rfloor 倒着枚举结点 i,进行 [i,n][i, n] 的调整。

  • 倒着枚举可以保证当前子树的根结点是最大值,使得建堆正确
1
2
3
4
5
void createHeap() {
for (int i = n / 2; i >= 1; i--) {
downAdjust(i, n);
}
}
  • 时间复杂度:O(n)O(n)

删除堆顶

删除堆顶较为简单,只需要将最后一个元素覆盖堆顶,然后重新向下调整堆

1
2
3
4
void deleteTop() {
heap[1] = heap[n--];
downAdjust(1, n);
}
  • 时间复杂度:O(logn)O(logn)

插入

在向上调整的基础上,可以很容易实现插入元素:

1
2
3
4
void insert(int x) {
heap[++n] = x;
upAdjust(1, n);
}
  • 时间复杂度:O(logn)O(logn)

应用

  • 堆排序:每次取出根结点,就能得到一个有序列了
文章作者: EasonZzZz
文章链接: http://yoursite.com/2021/04/04/数据结构/堆/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Nice To Meet U