斐波那契堆 & 题解：P11266 【模板】可并堆 2

题解里怎么没人讲斐波那契堆呢，多优美的数据结构啊。

在这里我们要实现一个斐波那契堆，部分思路来自此处。

截至本文发布时，本人在此题中的代码为最优解，已加入代码公开计划，但是强烈反对直接抄袭的行为。

首先我们要知道普通二叉堆都有哪些性质：

是一个完全二叉树。
没有孩子节点比父节点小。

这种堆插入元素，弹出最小值，减少元素的时间复杂度都为

O(\log n)

，但我们能做到更快吗？

我们可以尝试实现一个最简单的堆——就是一个集合，里面放着存入的元素，还有一个指向最小元素的指针。这样获取最小值只需要访问指针指向的元素就行了，插入元素时就直接把它放进去，然后判断是否需要更新最小值指针，减少元素也非常简单。但是弹出最小值时就有问题了，问题不是弹出它，而是如何快速找到新的最小值。

为了做到这一点，集合需要一定的结构来让我们快速找到最小值。但如果使用二叉堆，我们每次操作后要维护两条性质。但为了加速，我们需要一个没那么严格的结构，尽可能懒一点，非必要就不进行操作，但我们还得能快速求出最小值。

我们首先要去掉的是二叉堆的第一条性质，我们允许任意形态的树，甚至还可以有很多树，这些树用链表穿在一起，称为根链表。每个节点的孩子也用链表存储，这样我们可以快速插入和删除值（以上的链表都是双向循环链表）。

由于我们仍然满足堆的第二条性质，于是整个堆的最小值一点是树根之一，维护一个指针指向它。

加入我们弹出了最小值，那么新的最小值一定是之前的最小值节点的孩子或者是其他的树根，我们遍历上述节点来找到新的最小值。着就需要我们树的总数和每个节点的孩子数量（以下称为度）都相对比较少。

我们来实现一些操作。

插入一个元素最简单的方法就是把只有根节点的树直接加到根链表里，然后更新最小值指针，这样就完成了

O(1)

插入。合并两个堆只需要把它们的根链表并起来即可，时间复杂度

O(1)

。但是下一次弹出最小值时需要遍历大量节点，因为根链表里的节点都有可能成为下一个最小值。

但是我们可以在弹出的同时把一些小树合并成大树，反正我们也要遍历所有的根节点，这不会使时间复杂度变高，但可以显著减少树的数量，使以后的操作变快。

我们举个例子看看这种方式的效果如何。

例如我们向堆里插入了

100

个元素，然后弹出最小值，这会花费大量时间遍历所有根节点，但是后续的弹出操作会变得很快，因为我们清理了堆，使树根变少很多。

我们也可以从整体的角度分析，把弹出时遍历根的复杂度平均分到插入中，每个插入操作只会增加常数时间，但会使弹出操作的复杂度降低。

弹出最小值分为以下几步：

把最小值的孩子放在根链表中。
合并一些树。为了让树的度和树的个数都减少，我们可以不断合并相同度的树，直到每种度都只有一棵树。注意这个操作，这是保证复杂度的重要一步。
重建堆。重新维护根链表并记录最小值。

第一步的复杂度为节点的最大度，第二步的复杂度为节点的最大度加树的个数，第三步的复杂度也为节点的最大度。

树的个数可以均摊到之前的插入里，所以复杂度取决于节点的最大度，只要最大度小，那操作就会快。

我们看看在特定度数下最大的数是什么样子的。我们每次合并两颗相同度的树，两颗

0

度树（单点）合成

1

度树，两颗

1

度树合成

2

度树……这样我们就得到了一些二项树。根据合并时的操作可以得出二项树的子树还是二项树。

在弹出最小值时，我们把最小值节点的孩子放进根链表，再合并相同度的树，所以这些树一定都是二项树。

二项树的大小是指数增长的，每棵树的节点数都是前一颗的二倍，一颗

d

度树有

2^d

个节点，所以

n

个节点的堆只需要最大

\log_2n

度的树就可以存下。

所以，弹出最小值的复杂度被优化到了

O(\log n)

。

我们再来考虑如何减小一个元素的值。如果减小后不破坏堆的性质，那就什么都不用做，否则直接把它和它的子树扔进根链表里。

这看起来很好，清理时额外消耗的时间可以均摊到减小元素的操作上，但回顾我们之前的分析，弹出最小值的复杂度为对数是因为二项树的大小是指数增长的，但是如果我们随意把子树剪掉，那这些树就不是二项树了。最坏情况下

d

度树只会有

d+1

个节点，从对数增长变为了线性增长，这样弹出最小值的复杂度就出现了大问题。

如果我们不剪掉子树，那这样弹出最小值的复杂度是对了，但是减小元素却比较慢。如果我们剪掉子树，这样弹出最小值的复杂度可能很高。我们采取一种折中的方案，只允许一个节点剪掉一个孩子，剪掉一个孩子后就给它打上一个标记，如果再次给这个节点剪掉孩子就连带着把它自己也剪掉放在根链表里并取消标记。

这听起来不可思议，我们反而多剪掉了一些节点，但我们这么考虑：如果一棵树已经比它存的要少了，那么剪掉一些节点可能让它的度降低，这样就可以理所应当的存较少的节点了，这也使树不会离二项树太远。

我们来仔细分析一下复杂度：

假设我们减小了

n

次元素，最坏情况下只会剪下

2n

次节点，均摊一下每次复杂度还是

O(1)

的。每次平均只会增加两棵树，再把弹出最小值的操作均摊到减小元素操作上，复杂度仍然为常数。

现在只要证明树的度是对数增长即可。

之前说到

d

度树有

2^d

个节点，所以度数是对数的，所以问题变为判断树是不是指数增长的。

但是有减小元素操作后，树的形态不再是固定的，我们需要证明最坏的情况下树也是指数增长的。

假设每次合并把新子树放在右侧，每次合并相同度的树，所以第

i

个孩子至少有

i-1

度，就算再被剪掉一个节点，也至少有

i-2

度。

我们得出，一颗

d

度树至少也是由

0

度树加上

0

到

d-2

度树组成的。

设

f_d

表示

d

度数的最少的节点个数，根据上面的结论可以得出

f_0=1,f_1=2,f_d=1+f_0+\sum\limits_{i=0}^{d-2}f_i

，我们发现

f

其实是一个从

1,2

开始的斐波那契数列。

斐波那契数列是指数增长的，树的大小也是指数增长的，所以弹出最小值的复杂度仍然为

O(\log n)

。

最终，我们得到了完整的斐波那契堆，除了弹出最小值以外的操作的复杂度都是

O(1)

的堆，并且弹出最小值的复杂度也相当优，达到了基于比较的排序算法的复杂度下界。

参考实现：

CPP

class Node{
public:
	bool mark;
	int deg;
	ll key;
	Node *l,*r,*ch,*fa;
	Node(){
		key=deg=0,mark=false,l=this,r=this,ch=fa=nullptr;
	}
	Node(ll k){
		key=k,deg=0,mark=false,l=this,r=this,ch=fa=nullptr;
	}
};

class FibHeap{
	int cnt;
	Node *minp;
public:
	FibHeap(){
		cnt=0,minp=nullptr;
	}
private:
	void removep(Node *p){
		p->l->r=p->r;
		p->r->l=p->l;
	}
	void addp(Node *p,Node *rt){
		p->l=rt->l;
		rt->l->r=p;
		p->r=rt;
		rt->l=p;
	}
	Node* pushp(Node *p){
		if (cnt==0) minp=p;
		else{
			addp(p,minp);
			if (p->key<minp->key) minp=p;
		}
		cnt++;
		return p;
	}
	void megl(Node *u,Node *v){
		Node *t=u->r;
		u->r=v->r;
		v->r->l=u;
		v->r=t;
		t->l=v;
	}
	Node* removemin(){
		Node *t=minp;
		if (t==t->r) minp=nullptr;
		else{
			removep(t);
			minp=t->r;
		}
		t->l=t->r=t;
		return t;
	}
	void link(Node *p,Node *rt){
		removep(p);
		if (rt->ch==nullptr) rt->ch=p;
		else addp(p,rt->ch);
		p->fa=rt;
		p->mark=false;
		rt->deg++;
	}
	void megtrees(){
		int maxd=log(cnt)/log((1+sqrt(5))/2),n=maxd+1;
		Node **rt=new Node*[n];
		for (int i=0;i<n;i++) rt[i]=nullptr;
		while (minp!=nullptr){
			Node *u=removemin();
			int d=u->deg;
			for (;rt[d]!=nullptr;d++){
				Node *v=rt[d];
				if (u->key>v->key) swap(u,v);
				link(v,u);
				rt[d]=nullptr;
			}
			rt[d]=u;
		}
		minp=nullptr;
		for (int i=0;i<n;i++){
			if (rt[i]!=nullptr){
				if (minp==nullptr) minp=rt[i];
				else{
					addp(rt[i],minp);
					if (rt[i]->key<minp->key) minp=rt[i];
				}
			}
		}
		delete [] rt;
	}
	void cut(Node *p,Node *fa){
		removep(p);
		fa->deg--;
		if (p==p->r) fa->ch=nullptr;
		else fa->ch=p->r;
		p->fa=nullptr;
		p->l=p->r=p;
		p->mark=false;
		addp(p,minp);
	}
	void cutout(Node *p){
		p->mark=false;
		Node *fa=p->fa;
		if (fa!=nullptr){
			cut(p,fa);
			if (not fa->mark) fa->mark=true;
			else cutout(fa);
		}
	}
public:
	Node* push(ll k){
		return pushp(new Node(k));
	}
	void join(FibHeap *b){
		if (b==nullptr) return;
		if (minp==nullptr){
			minp=b->minp,cnt=b->cnt;
		}else if (b->minp!=nullptr){
			megl(minp,b->minp);
			if (minp->key>b->minp->key) minp=b->minp;
			cnt+=b->cnt;
		}
		b=nullptr;
	}
	void pop(){
		if (minp==nullptr) return;
		Node *m=minp;
		while (m->ch!=nullptr){
			Node *ch=m->ch;
			removep(ch);
			if (ch->r==ch) m->ch=nullptr;
			else m->ch=ch->r;
			addp(ch,minp);
			ch->fa=nullptr;
		}
		removep(m);
		if (m->r==m) minp=nullptr;
		else{
			minp=m->r;
			megtrees();
		}
		cnt--;
		m=nullptr;
	}
	ll top(){
		if (minp==nullptr) return 0;
		else return minp->key;
	}
	void decrease(Node *p,ll k){
		if (minp==nullptr or p==nullptr) return;
		p->key=k;
		Node *fa=p->fa;
		if (fa!=nullptr and p->key<fa->key) cutout(p);
		if (p->key<minp->key) minp=p;
	}
	void erase(Node *p){
		decrease(p,minp->key-1);
		pop();
	}
};

但是指针实现的斐波那契堆常数比较大，和 pbds 的配对堆速度差不多，我们可以把指针换成数组，再加上快读后成功抢到了最优解。

应用场景：

一种快一些的堆，插入和减小元素的复杂度都是

O(1)

，可以优化 dijkstra 算法求最短路至

O(n\log n+m)

。

斐波那契堆 & 题解：P11266 【模板】可并堆 2

文章操作

相关推荐

评论

斐波那契堆 & 题解：P11266 【模板】可并堆 2