Appearance
简介
二叉堆(Binary Heap
)是一种基于完全二叉树的数据结构。
- 小根堆:任意节点
其父节点,根节点最小; - 大根堆:任意节点
其父节点,根节点最大。
本篇以小根堆为例,介绍二叉堆的实现方式。
构造
按照从上到下,从左到右的顺序给节点编号。
该二叉堆具有以下性质:
号节点是根节点; 号的父节点为 (向下取整); 号的左子节点为 ,右子节点为 。 - 二叉堆的任意一条支路都按照升序排序。
使用数组保存二叉堆。
cpp
int t[], n;
// t[u] : u 号节点的值
// n : 节点总数
插入
如何往小根堆中插入元素
- 在堆底新建节点,值为
; - 对新节点所在支路进行排序.重复执行以下步骤。
- 若新节点
其父节点,则交换它们的位置,否则跳出循环。
- 若新节点
时间复杂度为
cpp
// 插入元素 val
void push(int val) {
t[++ n] = val; // 新建节点
for (int u = n; u != 1; u /= 2) {
if (t[u] < t[u / 2])
swap(t[u], t[u / 2]);
else break;
}
}
移除
将小根堆的根节点移除,如何调整使其仍为小根堆?
- 把堆底最后一个元素移到根节点;
- 从根节点
开始,重复执行以下步骤: - 比较
的两个子节点,取最小的一个,记为 ; - 若
,交换节点 和 的位置,并使 ,否则跳出循环。
- 比较
cpp
// 移除根节点
void pop() {
t[1] = t[n --];
for (int u = 1; 2 * u <= n; ) {
int v = 2 * u;
if (v + 1 <= n && t[v + 1] < t[v])
v ++; // 取最小的子节点
if (t[u] > t[v])
swap(t[u], t[v]), u = v;
else break;
}
}
模板
cpp
int t[], n;
void push(int val) {
t[++ n] = val;
for (int u = n; u != 1; u /= 2) {
if (t[u] < t[u / 2])
swap(t[u], t[u / 2]);
else break;
}
}
void pop() {
t[1] = t[n --];
for (int u = 1; 2 * u <= n; ) {
int v = 2 * u;
if (v + 1 <= n && t[v + 1] < t[v])
v ++;
if (t[u] > t[v])
swap(t[u], t[v]), u = v;
else break;
}
}