斐波那契堆学习笔记

· · 算法·理论

正文

斐波那契堆是一种可并堆，以小根堆为例，支持均摊 O(1) 插入节点、均摊 O(1) 减小节点值、均摊 O(\log n) 删除最小节点、以及均摊 O(1) 合并。

因为其复杂度为均摊，故不可持久化。

斐波那契堆维护了一个森林，其中每个节点的子节点个数都是 O(\log n) 级别的。（树高对斐波那契堆的复杂度没有影响）

如图为一个合法的斐波那契堆：（以小根堆为例）

其中用方框框住的就是整个堆中的最小节点，加粗的节点为打上标记的节点，标记含义为该节点是否已失去一棵子树，我们不允许一个非根节点失去多于一棵子树。

对于合并操作，可以直接将两个森林并在一起然后更新最小节点的指针，复杂度均摊为 O(1)。（下面将会说到一个斐波那契堆的所有根节点用一个双向链表维护，故合并时容易的）

对于插入节点操作，直接加入一个只有根节点的树即可，复杂度显然均摊为 O(1)。

对于减小节点值操作，直接将该节点与其父节点之间的边切断，并标记其父亲已失去一棵子树，然后更新最小节点的指针。（当然，如果操作的节点本身是一个根节点就只需要更新最小节点的指针）若其父节点在此操作之前已失去一棵子树，则需要将其父节点与其父节点的父节点之间的边切断，并不断向上递归，直到遇到一个根节点为止。下面几幅图展示了这个过程：

复杂度分析：每次操作至多给一个新的节点打上标记，至多取出一个未被打标记的节点，而一个被打标记的节点至多只被取出一次，取出一个节点只给整个斐波那契堆增加一个子树，于是复杂度均摊为 O(1)。（取出一个节点的复杂度容易做到 O(1)）

对于删除最小节点操作，将最小节点的所有子树都取出，然后需要保证每个根节点的儿子数互不相同，如果两个根节点的儿子数相同，则需要将值较大的根节点接到值较小的根节点下，使其称为值较小的根节点的子节点。最后更新最小节点的指针即可。下面几幅图展示了这个过程：

复杂度分析：用时显然为第一步结束后树的总数级别。由于删除最小节点操作以及插入节点操作时产生的树的数目已经被均摊到删除最小节点操作和插入节点操作上了，所以本操作的均摊复杂度就是上次合并后的树的数目以及最小值的子节点数的总和，显然与子节点最多的节点的子节点数同阶，我们将说明其为 O(\log n)。

显然我们希望在限制根节点的子节点的最大值为 x 的前提下构造合法的最小的斐波那契堆，记其节点数为 f_x。

为了让节点数最少，显然我们的斐波那契堆肯定只会有一棵树，有 x 个子节点。不难发现有 x 个子节点的堆是由两棵有 x-1 个子节点的堆合并得来的。然后我们让每个节点都尽可能失去一颗子树（除根节点以外），这样节点数最少。于是我们可以在合并后把作为儿子的有 x 个子节点的堆的最大的子树去除即可，那么我们就可以认为一个根有 x 个子节点的堆是由一个根有 x-1 个子节点的堆和一个根有 x-2 个子节点的堆合并而来。前几个堆是这样的：（省略最小节点标记，比较大的节点有标记）

那么我们有：

f_x=\left\{\begin{matrix}1&x=1\\2&x=2\\f_{x-1}+f_{x-2}&x>2\end{matrix}\right.

显然 f_x=F_{x+1}，其中 F_x 为斐波那契数列。（这也是斐波那契堆得名的由来）

众所周知，F_x=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^x-\left(\frac{1-\sqrt{5}}{2}\right)^x}{\sqrt{5}} 是指数级增长的，于是 n 个节点的斐波那契堆的子节点最多的节点的子节点数为 O(\log n) 量级的。

关于斐波那契堆的具体实现还需要注意以下几点：

  1. 存储斐波那契堆时每个节点需存储其左儿子（如果存在）、左右兄弟（根节点的左右兄弟也为根节点）和父节点（如果存在）的指针以便快速修改其形态。即一个节点的所有儿子组成一个双向链表，所有根节点也组成一个双向链表。
  2. 原则上，根节点不应被标记缺少一颗子树，所以将一个节点取出时记得将其标记清除。
  3. 在执行删除最小节点操作时可以准备一个指针数组存储目前子节点数为 i 的子树的根节点，然后扫一遍将所有子树插入其中，一旦出现冲突就合并。记得每次清空。

普通的斐波那契堆优化 dijkstra 复杂度可以达到 O(n\log n+m) 的最优复杂度。

使用斐波那契堆优化 dijkstra 做 P4779 的参考代码如下：（没有注释）

#include<cstdio>
using namespace std;
unsigned n,m,x[210000],y[210000],z[210000],num[110000],*mp[110000],*mpv[110000],dis[110000],a,i,j,k;
class node
{
    public:
    bool fl;
    node *fa,*ll,*rr,*lson;
    unsigned snum,wh,dis;
    node():fl(false),fa(NULL),ll(NULL),rr(NULL),lson(NULL),snum(0),wh(0),dis(0){}
}*heap[110000],*top,*c[40];
void out()
{
    unsigned i;
    node *s,*t,*z;
    while(top->snum>0)
    {
        s=top->lson;
        top->lson=s->rr;
        s->ll=top;
        s->rr=top->rr;
        s->ll->rr=s;
        s->rr->ll=s;
        s->fa=NULL;
        s->fl=false;
        top->snum--;
    }
    top->ll->rr=top->rr;
    top->rr->ll=top->ll;
    s=top->rr;
    delete top;
    if(s==top)
    {
        top=NULL;
        return;
    }
    top=s;
    for(i=0;i<=28;i++)
    c[i]=NULL;
    c[top->snum]=top;
    t=s->rr;
    while(1)
    {
        s=t;
        t=s->rr;
        if(c[s->snum]==s||s->fa!=NULL)
        break;
        if(c[s->snum]==NULL)
        {
            c[s->snum]=s;
            if(s->dis<top->dis)
            top=s;
            continue;
        }
        for(j=s->snum;;j++)
        {
            z=c[j];
            if(z==NULL)
            {
                c[j]=s;
                if(s->dis<=top->dis)
                top=s;
                break;
            }
            if(s->dis<z->dis)
            {
                z=s;
                s=c[j];
            }
            c[j]=NULL;
            z->snum++;
            s->fa=z;
            s->rr->ll=s->ll;
            s->ll->rr=s->rr;
            if(z->snum==1)
            {
                s->ll=s;
                s->rr=s;
            }
            else
            {
                s->rr=z->lson;
                s->ll=s->rr->ll;
                s->rr->ll=s;
                s->ll->rr=s;
            }
            z->lson=s;
            s=z;
        }
    }
}
void update(node *s)
{
    node *p=s->fa;
    if(p==NULL)
    return;
    if(s->fl==false)
    {
        s->fl=true;
        return;
    }
    s->fl=false;
    p->snum--;
    if(p->lson==s)
    if(p->snum==0)
    p->lson=NULL;
    else
    p->lson=s->rr;
    if(p->snum>0)
    {
        s->rr->ll=s->ll;
        s->ll->rr=s->rr;
    }
    s->ll=top;
    s->rr=top->rr;
    s->rr->ll=s;
    s->ll->rr=s;
    s->fa=NULL;
    update(p);
}
void up(unsigned wh)
{
    node *p=heap[wh]->fa;
    if(p==NULL)
    {
        if(heap[wh]->dis<top->dis)
        top=heap[wh];
        return;
    }
    heap[wh]->fl=false;
    p->snum--;
    if(p->lson==heap[wh])
    if(p->snum==0)
    p->lson=NULL;
    else
    p->lson=heap[wh]->rr;
    if(p->snum>0)
    {
        heap[wh]->rr->ll=heap[wh]->ll;
        heap[wh]->ll->rr=heap[wh]->rr;
    }
    heap[wh]->ll=top;
    heap[wh]->rr=top->rr;
    heap[wh]->rr->ll=heap[wh];
    heap[wh]->ll->rr=heap[wh];
    heap[wh]->fa=NULL;
    if(heap[wh]->dis<top->dis)
    top=heap[wh];
    update(p);
}
main()
{
    scanf("%u%u%u",&n,&m,&a);
    for(i=1;i<=m;i++)
    {
        scanf("%u%u%u",&x[i],&y[i],&z[i]);
        num[x[i]]++;
    }
    for(i=1;i<=n;i++)
    {
        mp[i]=new unsigned[num[i]+1];
        mpv[i]=new unsigned[num[i]+1];
        mp[i][0]=0;
    }
    for(i=1;i<=m;i++)
    {
        mp[x[i]][0]++;
        mp[x[i]][mp[x[i]][0]]=y[i];
        mpv[x[i]][mp[x[i]][0]]=z[i];
    }
    for(i=1;i<=n;i++)
    dis[i]=2147483647;
    dis[a]=0;
    for(i=1;i<=n;i++)
    heap[i]=new node;
    for(i=1;i<=n;i++)
    heap[i]->wh=i;
    for(i=1;i<=n;i++)
    heap[i]->dis=dis[i];
    for(i=1;i<n;i++)
    heap[i]->rr=heap[i+1];
    heap[n]->rr=heap[1];
    for(i=2;i<=n;i++)
    heap[i]->ll=heap[i-1];
    heap[1]->ll=heap[n];
    top=heap[a];
    for(i=1;i<=n;i++)
    {
        k=top->wh;
        out();
        for(j=1;j<=mp[k][0];j++)
        if(dis[k]+mpv[k][j]<dis[mp[k][j]])
        {
            dis[mp[k][j]]=dis[k]+mpv[k][j];
            heap[mp[k][j]]->dis=dis[mp[k][j]];
            up(mp[k][j]);
        }
    }
    for(i=1;i<=n;i++)
    printf("%u ",dis[i]);
}

关于常数：

效率对比（均选择 C++14 (GCC 9) 语言并开启 O2 优化） 斐波那契堆优化 dijkstra（O(n\log n+m)） 二叉堆优化 dijkstra（O(m\log n)）
P3371（n\le10^4,m\le5\times10^5，数据随机） 总 334\text{ms}，最大 85\text{ms} 总 458\text{ms}，最大 117\text{ms}
P4779（n\le10^5,m\le2\times10^5） 总 396\text{ms}，最大 82\text{ms} 总 386\text{ms}，最大 82\text{ms}

看到表格第二行，就可以发现斐波那契堆常数也没有很多人想象中那样大，甚而至于只有 m 比 n 大很多时才速度相当。

看到表格第一行，其实斐波那契堆在数据随机的时候常数才显得大，因为二叉堆上浮的过程时间可能会少很多，但斐波那契堆复杂度几乎时时卡满。

闲话

其实是在做 P1576 的时候学的斐波那契堆，还写了题解，结果后来管理员告诉我不需要使用高精度……

于是我想着不能浪费，就把题解里面关于斐波那契堆的部分搬了过来。