模板 – 支持单点修改与删除操作的二叉堆

昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。

具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$\mathrm{O}(\log n)$地修改和删除特定节点，以及常规的$\mathrm{O}(\log n)$的弹出栈顶、插入等操作，$\mathrm{O}(1)$地查询堆顶元素。

下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define inl inline
#define SIZ 100000
struct degree {
	int deg, x;
	friend bool operator < (degree a, degree b) {
		return a.deg < b.deg; }
};
struct biheap {
	degree h[SIZ]; int ed, son, id[SIZ]; // 保存指针 
	inl void clear () { ed = 0; }
	inl degree top () { return h[1]; }
	inl void up (int ima) {
		while (ima > 1 && h[ima] < h[ima>>1])
			id[h[ima].x] = ima>>1, id[h[ima>>1].x] = ima, // 交换指针 
			swap (h[ima], h[ima>>1]), ima >>= 1;
	}
	inl void down (int ima) {
		while (ima<<1 <= ed) {
			son = ima<<1;
			if (son < ed && h[son + 1] < h[son]) ++son;
			if (h[son] < h[ima])
				id[h[ima].x] = son, id[h[son].x] = ima, // 交换指针 
				swap (h[ima], h[son]), ima = son;
			else break;
		}
	}
	inl void pop () {
		id[h[1].x] = 0; h[1] = h[ed--]; // 交换堆末尾元素和堆顶，向下调整 
		id[h[1].x] = 1; down (1); }
	inl void ins (degree a) {
		h[++ed] = a; id[a.x] = ed; up (ed); }
	inl void modify (int ima, int delta) { // 单点修改 
		ima = id[ima]; h[ima].deg += delta;
		up (ima); down (ima); } // 可能需要向上或向下调整才能满足堆性质
	inl void remove (int ima) {
		ima = id[ima]; id[h[ima].x] = 0;
		h[ima] = h[ed--]; id[h[ima].x] = ima;
		up(ima); down (ima); }
	inl int size () { return ed; }
} q;