简介

二叉堆（Binary Heap）是一种基于完全二叉树的数据结构。

• 小根堆：任意节点 $\ge$ 其父节点，根节点最小；
• 大根堆：任意节点 $\le$ 其父节点，根节点最大。

本篇以小根堆为例，介绍二叉堆的实现方式。

构造

按照从上到下，从左到右的顺序给节点编号。

该二叉堆具有以下性质：

• $1$ 号节点是根节点；
• $u$ 号的父节点为 $\frac{u}{2}$（向下取整）；
• $u$ 号的左子节点为 $2u$，右子节点为 $2u+1$。
• 二叉堆的任意一条支路都按照升序排序。

使用数组保存二叉堆。

int t[], n;
// t[u] : u 号节点的值
// n : 节点总数

插入

如何往小根堆中插入元素 $2$？

1. 在堆底新建节点，值为 $2$；
2. 对新节点所在支路进行排序.重复执行以下步骤。
   • 若新节点 $<$ 其父节点，则交换它们的位置，否则跳出循环。

时间复杂度为 $O(n\log n)$。

// 插入元素 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;
	}
}

移除

将小根堆的根节点移除，如何调整使其仍为小根堆？

1. 把堆底最后一个元素移到根节点；
2. 从根节点 $u=1$ 开始，重复执行以下步骤：
   • 比较 $u$ 的两个子节点，取最小的一个，记为 $v$；
   • 若 $t[u]>t[v]$，交换节点 $u$ 和 $v$ 的位置，并使 $u=v$，否则跳出循环。

// 移除根节点
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;
	}
}

模板

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;
	}
}