发布于 ，更新于 

配对堆基本介绍

飞快的可并堆

时间复杂度

还没有完全严格的证明，但一般认为配对堆时间复杂度如下：
删除堆顶均摊 \(\operatorname{O}(\log n)\)
插入元素 \(\operatorname{O}(1)\) 合并 \(\operatorname{O}(1)\)

貌似这个可能比斐波那契堆快（

节点存储

配对堆不是一个二叉树，一般采用“左儿子右兄弟”表示法，一个节点存储自己第一个儿子与右侧第一个兄弟。
有点抽象？实际上相当于每一个节点的儿子使用链表维护，然后该节点连着第一个子节点。

代码就非常好写了

1
2
3
4
struct Node {
	int val;
	Node *child, *nex; // 第一个儿子，下一个兄弟
};

合并两个堆

比较根节点大小，把根节点大的堆直接改成根节点小的堆根节点的儿子即可。
图示中还是使用树本身形态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node* meld(Node* x, Node* y) {  // 传入两个根节点
	if (x == null) // null 为空节点
		return y;
	else if (y == null)
		return x;
	if (x->val < y->val) { // x 比 y 小，y 当 x 的儿子
		y->nex = x->child; // 旧儿子是新儿子的兄弟
		x->child = y; // 新儿子是第一个儿子
		return x;
	} else {
		x->nex = y->child;
		y->child = x;
		return y;
	}
}

插入新节点

新建节点，然后当成两个堆合并即可。

1
2
3
4
5
6
7
8
void push(int x) {
	Node* y = new_node(); // 获取新节点
	y->val = x;
	if (root == null) // 当前堆为空的话，新节点为根
		root = y;
	else
		root = meld(root, y); // 否则当成两个堆合并
}

弹出堆顶

貌似要写完了，但是前面几个操作都没有对堆的性质进行维护，因此重头戏在这个部分...

删除根节点之后，遇到的是原来的子节点们组成的森林，想办法把它们合并到一起。
有了上面的合并操作，很容易想到将这些森林里的树一棵一棵合并的方法，但是这样时间复杂度就奔 \(\operatorname{O}(n)\) 去了，因为每次删除根节点都只是单纯地把子节点比较一遍，非常缓慢。
于是说到了该数据结构名称的由来——“配对”。
我们把这个森林两两配对之后再合并成一个新堆，于是理想状态下，多次删除根结点，新根节点的子节点数量将为 \(2\)，均摊时间复杂度大约是 \(\operatorname{O}(\log n)\) 的。

图示过程：

首先实现一个用于配对的函数。

1
2
3
4
5
6
7
Node* merges(Node* x) {
	if (x == null || x->nex == null) return x;  // x 为空或者 x 没有下一个兄弟节点
	Node* y = x->nex;                           // y 是 x 的下一个兄弟
	Node* c = y->nex;                           // c 是再下一个兄弟
	x->nex = y->nex = null;                     // 拆散
	return meld(merges(c), meld(x, y));         // x 与 y 配对在一起，剩下的继续配对
}
然后弹出堆顶的操作就很好写了。
1
2
3
4
5
void pop() {
	Node* t = merges(root->child);
	remove(root);
	root = t;
}

模板

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using i64 = long long;

#define __SIZ 2000006

struct Node {
    i64 val;
    Node *child, *nex;
} tree[__SIZ], *rubbish_bin[__SIZ]; // 提早分配内存，new 太慢了
Node *null = tree, *tot = tree;
i64 bintop;

class pairing_heap {
    Node* root;

    Node* new_node() {
        Node* nod;
        if (bintop)
            nod = rubbish_bin[bintop--]; // 垃圾回收
        else
            nod = ++tot;
        nod->child = null;
        nod->nex = null;
        return nod;
    }

    void remove(Node* x) {
        rubbish_bin[++bintop] = x;
    }

    Node* meld(Node* x, Node* y) {  // 合并两个堆
        if (x == null)
            return y;
        else if (y == null)
            return x;
        if (x->val < y->val) {
            y->nex = x->child;
            x->child = y;
            return x;
        } else {
            x->nex = y->child;
            y->child = x;
            return y;
        }
    }

    Node* merges(Node* x) {
        if (x == null || x->nex == null) return x;  // x 为空或者 x 没有下一个兄弟节点
        Node* y = x->nex;                           // y 是 x 的下一个兄弟
        Node* c = y->nex;                           // c 是下一个兄弟
        x->nex = y->nex = null;                     // 拆散
        return meld(merges(c), meld(x, y));         // x 与 y 配对在一起，剩下的继续配对
    }

public:
    pairing_heap() {
        root = null;
    }
    void push(i64 x) {
        Node* y = new_node();
        y->val = x;
        if (root == null)
            root = y;
        else
            root = meld(root, y);
    }
    i64 top() {
        return root->val;
    }
    void pop() {
        Node* t = merges(root->child);
        remove(root);
        root = t;
    }
} q;

许可协议

本文采用 GNU 自由文档许可证 许可协议，转载请注明出处。

分享文章