Data Structure 06 - Binary Heap
# 前置知识
在阅读本文档前,请确保你已经掌握堆的基本概念,详见 Data Structure 知识板块中的 05 - Heap 文档。
# 基本概念
二叉堆 (Binary Heap) 是一种满足堆性质的完全二叉树。
二叉堆可以高效地支持如下基本功能:
插入操作:向堆中插入一个元素,并维持堆性质。
查询最值操作:获取堆顶元素,即获取堆中的最大值(或最小值)。注意通常只允许访问堆顶元素的键值。
弹出操作:将堆顶元素取出,并维持堆性质。注意通常只允许取出堆顶。
下图是一个二叉堆的例子。这是一个大顶堆。
二叉堆是最基础、最简单的堆的实现方式,并且能满足多数的使用需求,但有时它是无法胜任的,详见下文中的介绍。
为便于描述,设二叉堆的根节点的下标为 ,设 表示节点 的键值。
本文中的内容均以大顶堆为例,并使用顺序存储的方式:
// 定义
const int MAX = ...;
int heap[MAX];
int n = 0;
这里复习一下完全二叉树的基本知识:如果设根节点的下标为 ,那么对于树上任意一个节点 ,其左子节点为 ,右子节点为 ,父节点为 。为方便起见,我们将父节点简记为 ,这也符合 C/C++ 语言中整数类型的运算规则。
注:对于二叉堆而言,大顶堆/小顶堆有时也被称为大根堆/小根堆,因为二叉堆的基础结构是树。但是这种称呼方式并不适合用于那些使用森林结构的堆,如二项堆等。
# 基本操作
为便于理解,我们先在已经存在一个二叉堆的基础上,考虑如何进行插入和弹出操作,再考虑如何建立一个二叉堆。
# 插入操作
二叉堆执行插入操作的方法是,在堆的末尾处(也就是下标为 的、目前为空的位置)插入元素,然后对堆进行调整,将新节点不断和父节点进行比较和交换,直到重新满足堆性质为止。
具体地讲,插入操作可分为如下步骤:
在堆的末尾处插入元素,记其下标为 ,初始为 。然后令 。或是先令 再令 ,这不重要。
将 与它的父节点 比较,如果 ,则说明当前不满足堆性质,将 与 交换。下标 变为 。该过程被称为 向上筛选 (sift-up) 。
重复步骤 2 ,直到 为止,说明当前满足堆性质,插入操作完成。
插入操作如下图所示,其中紫色的节点表示新插入的元素,蓝色的边表示当次参与比较或交换的边。
现在我们考虑插入操作的具体原理及其正确性。
其一,当我们把新元素插入到叶子节点处时,不仅无需先挪动堆中其它节点,而且整个堆上仅仅从新节点到根节点的这条路径上的这些节点可能会失去堆性质,而堆中其他节点的堆性质不受影响,因为只有这些节点是新节点的祖先节点。
其二,每次将 和父节点 交换后,在 原先的 下标 处,以 为根节点的子树一定满足堆性质,因此可能不满足堆性质的节点个数必定会 。
其三,一旦当前 成立,就意味着 的更上层的祖先节点也都将满足堆性质,无需继续调整。因为在 被插入前,堆中所有节点都满足堆性质,也就是说 ,由此递推可知结论成立。
由于二叉堆是一棵完全二叉树,树的高度不超过 ,因此最多向上调整 次即可保证满足堆性质,所以插入操作的时间复杂度为 。
下面是插入操作的代码实现。
// 插入
void push(int value) {
heap[++n] = value;
sift_up(n);
}
// 向上筛选
void sift_up(int index) {
// 主循环
while (index > 1) {
// 获取父节点
int parent = index / 2;
// 满足堆性质的情况
if (heap[parent] >= heap[index]) {
break;
}
// 交换
swap(heap[parent], heap[index]);
index = parent;
}
}
# 弹出操作
二叉堆执行弹出操作的方法是,获取堆顶元素后,将堆的末尾元素(也就是下标为 的位置)移至堆顶位置,然后对堆进行调整,将新节点不断和子节点进行比较和交换,直到重新满足堆性质为止。
具体地讲,弹出操作可分为如下步骤:
获取堆顶元素,然后将堆的末尾元素移至堆顶位置,记其下标为 ,初始为 。然后令 。
将 与它的两个子节点 比较,如果 ,则说明当前不满足堆性质,将 与子节点 中的较大者交换。下标 变为 或 。该过程被称为 向下筛选 (sift-down) 。
重复步骤2,直到 为止,说明当前满足堆性质,弹出操作完成。
弹出操作如下图所示,其中紫色的节点表示在弹出堆顶后被上移至根节点处的元素,蓝色的边表示当次参与比较或交换的边。
弹出操作的原理和插入操作类似,只是插入是自下而上调整,弹出是自上而下调整,读者可自行理解,用类似的方法予以证明,此处不予赘述。
类似于插入操作,弹出操作的时间复杂度为 。
下面是弹出操作的代码实现。
// 弹出
void pop() {
heap[1] = heap[n];
n --;
sift_down(1);
}
// 向下筛选
void sift_down(int index) {
// 主循环
while (2*index <= n) {
// 获取子节点中的较大者
int lson = 2*index, rson = 2*index + 1;
int child;
if (rson <= n && heap[rson] > heap[lson]) {
child = rson;
} else {
child = lson;
}
// 满足堆性质的情况
if (heap[index] >= heap[child]) {
break;
}
// 交换
swap(heap[index], heap[child]);
index = child;
}
}
# 查询最值操作
对于二叉堆来说,取出堆中最大元素是一件很简单的事情。
// 查询最值
int top() {
return heap[1];
}
此外,有些地方的二叉堆的实现会在 pop()
时获取堆顶,即在弹出的同时执行一次查询,代码实现可能如下所示,这与前文所述的弹出的实现方式没有本质上的区别。
// 弹出(先查询最值)
int pop() {
int val = heap[1];
heap[1] = heap[n];
n --;
sift_down(1);
return val;
}
# 建堆
现在我们考虑如何由一个长为 的乱序数组 构建一个堆。
显然,最简单粗暴的办法就是执行 次插入,时间复杂度为 。但是我们有办法可以在 的时间内进行建堆。该算法是由 Floyd 提出的,通常称为 筛选法建堆 。
# 算法流程
筛选法建堆的过程很简单,就是倒序遍历整个堆,对每个节点 执行一次向下筛选的操作。这个遍历节点的过程是自下而上的,要严格按照层序进行。
考虑到对叶子节点执行向下筛选是没有意义的,实际上只需从编号为 的节点开始倒序遍历即可,因为 是最后一个节点,它的父节点即为编号最大的非叶子节点。
// 建堆
void build() {
for (int index = n / 2; index >= 1; index --) {
sift_down(index);
}
}
# 正确性证明
下面简要证明该算法的正确性。
我们用类似归纳法的方式证明,每对一个节点 执行完向下筛选的操作,即可保证以节点 为根节点的子树满足堆性质。
对于叶子节点,显然成立。
对于高度为 的子树,显然成立。
因为是倒序遍历,事实上也是按层遍历,当节点 被遍历到的时候,其左右子树,即以 为根节点的子树,一定已经被遍历到。
我们假设这些小一级的子树已经满足堆性质,那么在以 为根节点的子树中,从结果上来看,其结构等价于之前我们的删除操作,那么根据前文所述的原理可知,我们只要对 进行调整即可将该子树调整至满足堆性质。正确性得证。
# 时间复杂度分析
从直觉上,你可能会认为筛选法建堆的时间复杂度为 ,因为要遍历 个节点,每个节点都要进行一次形如删除操作的向下筛选,而删除操作的时间复杂度为 。事实上这是不对的。
需要认清楚的是,无论是向上还是向下,筛选操作的时间复杂度为 ,其中 为树的高度。在插入和删除操作中,执行的筛选操作是 sift_up(n)
和 sift_down(1)
,都是对整个堆进行的,即 。而在建堆过程中,每次是对以 为根节点的子树进行的,执行的筛选操作是 sift_down(i)
。
下面我们详细分析为什么筛选法建堆的时间复杂度为 。我们直接计算最大情况,因此将 记为 ,这不影响结果。
回顾一下二叉树的基本性质,对于二叉树而言,树的第 层上最多有 个节点,其中树的根节点为第 层。那么:
深度为 的节点个数为 。
以深度为 的节点为根节点的子树的高度为 ,也就是说,子树高度为 的节点的深度为 ,因此这样的节点个数最多为 。
所以,这些节点执行筛选操作的总时间为:
因为级数 收敛,所以我们可以认为 是一个常数,因此总的时间复杂度为 。
# 优缺点分析
二叉堆的优点就是堆的基本特征,提供快速取出数据集中的最值的功能,以及快速更新并同时维持堆性质不变的功能。此外,二叉堆具有简单易懂的特点,并且其功能足以满足多数情况下的效率要求。
二叉堆的缺点是无法快速地将若干个堆合并。合并两个二叉堆的时间复杂度为 ,其中 为两个堆的大小。即便使用启发式合并也是 的,当 的数量级相近时并无太大意义。当我们需要分多次合并若干个堆的时候,二叉堆显然无法胜任。在这种情况下,我们需要使用任意一种可并堆,详见后续的教程。
# 应用
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01