二叉堆的实现

概念与存储

二叉堆是一棵完全二叉树，且分为大根堆和小根堆。对于大根堆，其父结点的值大于等于子节点。

由于是完全二叉树，所以就可以用 $2i,2i+1$ 访问左右结点，$\lfloor i/2\rfloor$ 访问父节点（根初始编号为 $1$）

int h[N];
int cnt; // 节点个数

获得最大值/最小值

由定义可知，对于大根堆/小根堆，h[1] 就是其最大值/最小值。

int top() {
	return h[1];
}

插入元素

以大根堆为例。首先，我们把元素放进树的尾部。但是我们发现，这样有可能违反父节点大于等于子节点的性质，于是我们需要“修复”。

修复的过程是：如果自己就是整棵树的根，或者父节点的值比自己大，则停止；否则，将自己的值与父结点交换，然后对父节点递归进行同样操作（想象为向上攀爬）

void up(int x) {
	if (x == 1 || h[x] < h[x / 2]) return; // 已经是根或父节点大于等于自己，返回
	swap(h[x], h[x / 2]); // 交换
	up(x / 2); // 对父节点进行操作
}

void push(int x) {
	h[++cnt] = x; // 节点数量增加，然后加入 x
	up(cnt); // 对这个新增节点进行修复操作
}

根据完全二叉树的高度，可以知道操作是 $O(\log n)$ 的。

删除元素