摆子复活了。

摆子写了篇笔记。

摆子又死了。

前言

为了做ADS的Project学的。难度堪比LCT，不过还是比红黑树略逊一筹。

斐波那契堆拥有及其优秀的理论复杂度：$O(1)$插入和减小键值，$O(\log n)$删除最值。然而也只是理论复杂度了。实际上堆里的斐波那契堆就好比平衡树里的splay，有个巨大的常数，所以只是个嘴巴算法。

抄袭来源

https://blog.51cto.com/u_13393656/5093051

https://blog.csdn.net/Foliciatarier/article/details/57472656

https://www.luogu.com.cn/blog/Atalod/learning-note-fibonacci-heap#

#define

$key$：节点排序的键值
度数：节点的儿子数
$flag$：Decrease Key中使用的标记，用于记录该节点是否有儿子被剪切过。加入根链表中的节点自动清空$flag$。
$fib_n$：斐波那契数列第n项

斐波那契堆

以最小堆为例。

斐波那契堆跟二项堆很像，是由多个最小堆组成的森林。所有堆的根节点用循环双向链表链接，形成根链表。额外存储一个指针$\min$指向根链表中$key$最小的节点。

偷一张图：

Insert

往斐波那契堆中插入一个新节点。

直接把节点插入到根链表的结尾。因为根链表是循环双向链表，所以直接插入到$\min$的前一位即可。之后检查新节点的$key$是否小于$\min$的$key$，如果是则更新$\min$为新节点。

Delete Min

删除斐波那契堆中$key$最小的节点（即$\min$节点）。

首先新建一个临时存放子树的区域，叫做temp区域。把$\min$的所有子节点和根链表中$\min$以外的节点进行以下操作：

将节点带着其子树加入temp区域
检查temp区域中是否存在度数相同的树，如果有，合并两棵子树。具体的说，把$key$较小的根节点作为父，$key$较大的作为子，建立父子关系。
重复第2步直到不存在度数相同的树

随后，把temp区域中所有根节点用链表链接作为新的根链表，并更新$\min$节点，此时temp区域里即为删除完成的堆。

再偷一张图：

Decrease Key

将斐波那契堆中指定节点的$key$减小。

如果减小后的$key$仍然比父节点的$key$大，则啥都不用做。

否则该节点违反了堆的性质，执行以下“级联剪切”操作：

如果目标节点在根链表中，退出
断开目标节点与其父节点的父子关系
将目标节点带着子树加入根链表中，并更新$\min$节点
如果目标节点原来的父节点的未被标记$flag$，则标记；否则清除其标记并对其进行级联剪切

~~图不好，不偷了~~

其他

斐波那契堆还支持合并、Increase Key、删除任意节点等操作。因为Dijstra用不到就不写了懒。

复杂度

假设有一斐波那契堆$H$，定义其势函数为$\Phi(H)=t(H)+2m(H)$，其中$t(H)$为根链表中节点的数目，$m(H)$为堆中被标记节点的数目。操作后$H$变为$H’$。

则进行一次操作的摊还代价为$T+\Phi(H’)-\Phi(H)$，其中$T$为该次操作实际代价。

Insert

一眼丁真，鉴定为$O(1)$。

Delete Min

假设在有$n$个节点的斐波那契堆中，任意节点的最大度数为$D(n)$。

在删除操作中，我们先是提取出删除节点的子节点加入temp区域（最多有$D(n)$个），再把根链表的节点全部加入temp区域（有$t(H)-1$个）。其中，由于合并两棵树是$O(1)$的，所以加入temp区域这一操作是$O(1)$的，则实际代价为$O(D(n)+t(H))$

删除后，势函数最坏情况为没有被标记节点加入根链表（否则$m(H’)$会减少）。因为相同度数的节点都被合并了，所以删除后根链表最多有$D(n)$个节点，则操作后势函数为$D(n)+2m(H)$。

一个sb问题：为什么删除后根链表最多有$D(n)$个节点？

A：因为删除后根链表里的节点度数两两不同，而$D(n)$定义就是根链表中最大的度数，所以最坏情况下就是度数为$1,2,\dots D(n)$的节点各有一个，最多$D(n)$个

摊还代价为$\\O(D(n)+t(H))+D(n)+2m(H)-t(H)-2m(H)\\=O(D(n))+D(n)+O(t(H))-t(H)\\=O(D(n))$

接下来问题变为$D(n)$是多少。

假设度数为$k$的节点最少有$f_k$个节点。一个度数为$k$的节点$p$可以拆分成一个度数为$k-1$的节点和其度数最大的子节点$p_{max}$。

由于只有在删除操作中两个节点度数相同时会建立父子关系，且操作后父节点度数只会+1，所以$p$的子节点度数为$1,2,\dots k-1$（不考虑Decrease Key）。考虑Decrease Key操作，因为一个子节点最多会删掉一个孙子节点（再删就被切走了），所以$p_{max}$的度数最小为$k-2$。

又一个sb问题：但是$p$也可能删掉子节点，如果把$p_{max}$删掉了，最大度数就不是$k-2$了。

A：删掉后$p$的度数也会-1啊…

综上，有$f_k\ge f_{k-1}+f_{k-2}$。

这个式子跟斐波那契数列很像，于是有$f_k\ge fib_k$。

即度数为$k$的节点子树最少有$fib_k$个节点。而斐波那契数列增长速度是指数级的，所以$D(n)=O(\log n)$，即删除操作均摊复杂度为$O(\log n)$。

Decrease Key

显然一次剪切操作是$O(1)$。

如果修改后违反了堆的性质：

还是用势函数分析。

假设一次操作触发了$c$次剪切，则实际代价为$O(c)$。根链表中多了被剪切的$c$个节点，则$t(H’)=t(H)+c$。除了剪切被修改节点，其余每次剪切清除一个标记，最后一个被剪切的节点的父节点可能被标记，则$m(H’)=m(H)-c+2$。

所以摊还代价为$\\O(c)+t(H’)+2m(H’)-t(H)-2m(H)\\=O(c)+t(H)+c+2m(H)-2c+4-t(H)-2m(H)\\=4\\=O(1)$

优化Dijstra

传统的堆优化Dijstra是靠插入新节点和打标记来实现Decrease Key的，所以复杂度在$m$上有个$\log$。

但是斐波那契堆可以在更新$dis$时直接对对应节点进行$O(1)$的$Decrease Key$，复杂度为$O(n\log n+m)$。并且由于该操作不增加新的节点，所以可以保证堆的空间复杂度从$O(m)$变为$O(n)$。~~虽然存边还是有个O(m)的空间~~

代码

基本纯手搓，很丑常数大还可能有bug。不过至少能跑过洛谷的最短路。

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100005
#define INF 0x7f7f7f7f

/*----- Fibonacci堆 声明 BEGIN -----*/ 
struct FibonacciNode{
    struct FibonacciNode *left;//根链表的前驱或左兄弟
    struct FibonacciNode *right;//根链表的后继或右兄弟
    struct FibonacciNode *fa;//父节点
    struct FibonacciNode *child;//第一个孩子
    int key;//权值
    int ref;//该节点代表的图中的节点 
    int flag;//标记
    int degree;//度数
};
typedef FibonacciNode *FibNode;
FibNode min;
FibNode temp_min;//删除时使用的临时最小节点
FibNode temp[MAXN];//删除时使用的临时数组，temp[i]存储当前度数为i的节点
int max_degree;//删除时记录的最大度数
int max(int a,int b);
FibNode newNode(int key);//创建一个新节点，权值为key
void swap(FibNode *a,FibNode *b);
void link(FibNode pre,FibNode next);//连接两个节点，pre在前，next在后
void cut(FibNode p);//级联剪切节点p
void mark(FibNode p);//标记节点p，若已被标记则级联剪切p
void addNode(FibNode p);//将节点p插入到根链表中
void addTemp(FibNode p);//将节点p加入进temp数组中
void addChild(FibNode fa,FibNode ch);//将节点ch设为节点fa的儿子
int getMin();//获取堆中最小值对应的图中节点编号 
int isEmpty();//询问当前堆是否为空 
FibNode insert(int key,int ref);//插入一个节点，权值为key，代表图中节点ref 
void deleteMin();//删除最小节点
void decreaseKey(FibNode p,int key);//将节点p的权值改为key，且保证新的key比原来小
/*----- Fibonacci堆 声明 END -----*/ 

/*----- Dijstra 声明 BEGIN -----*/ 
struct EdgeNode{
    struct EdgeNode *next;
    int v,l;
};
typedef EdgeNode *Edge;
Edge first[MAXN];
FibNode node[MAXN];//图中节点在堆中对应的节点 
int n,m,s;//节点数，边数，起点 
int dis[MAXN];
void addEdge(int x,int y,int l);
void dijstra();
/*----- Dijstra 声明 END -----*/ 

int main(){
    scanf("%d%d%d",&n,&m,&s);
    while(m--){
        int x,y,l;
        scanf("%d%d%d",&x,&y,&l);
        addEdge(x,y,l);
    }
    dijstra();
    for(int i=1;i<=n;++i)
        printf("%d ",dis[i]);
}

/*----- Fibonacci堆 定义 BEGIN -----*/ 
int max(int a,int b){return a>b?a:b;}
FibNode newNode(int key){
    FibNode p=(FibNode)malloc(sizeof (struct FibonacciNode));
    p->left=p->right=p;
    p->fa=p->child=NULL;
    p->key=key;
    p->flag=0;
    p->degree=0;    
}
void swap(FibNode *a,FibNode *b){
    FibNode temp=*a;
    *a=*b;
    *b=temp;
}
void link(FibNode pre,FibNode next){
    pre->left=next->left;
    next->left->right=pre;
    next->left=pre;
    pre->right=next;
}
int getMin(){
    return min->ref;
}
int isEmpty(){
    return min==NULL;
}
void cut(FibNode p){
    if(p->fa==NULL)return;
    if(p->fa->child==p){
        p->fa->child=p->right;
        if(p->right!=NULL)p->right->left=NULL;
    }
    else {
        p->left->right=p->right;
        if(p->right!=NULL)p->right->left=p->left;
    }
    mark(p->fa);
    p->fa=NULL;
    addNode(p);
}
void mark(FibNode p){
    if(p->fa==NULL)return;
    if(p->flag)cut(p);
    else p->flag=1;
}
void addNode(FibNode p){
    p->flag=0;
    if(min==NULL)min=p->left=p->right=p;
    else{
        link(p,min);
        if(min->key>p->key)min=p;
    }
}
void addTemp(FibNode p){
    int d=p->degree;
    p->left=p->right=p;
    p->fa=NULL;
    if(temp[d]==NULL){
        max_degree=max(max_degree,d);
        temp[d]=p;
    }
    else {
        if(temp[d]->key>p->key)swap(&temp[d],&p);
        addChild(temp[d],p);
        addTemp(temp[d]);
        temp[d]=NULL;
    }
}
void addChild(FibNode fa,FibNode ch){
    if(fa->child!=NULL){
        ch->right=fa->child;
        fa->child->left=ch;
    }
    else ch->right=NULL;
    fa->child=ch;
    ch->left=NULL;
    ch->fa=fa;
    max_degree=max(max_degree,++fa->degree);
}
FibNode insert(int key,int ref){
    FibNode p=newNode(key);
    p->ref=ref;
    addNode(p);
    return p;
}
void deleteMin(){
    max_degree=0;
    temp_min=NULL;
    if(min->child!=NULL)
        for(FibNode p=min->child,next=p;p!=NULL;p=next)next=next->right,addTemp(p);
    for(FibNode p=min->right,next=p->right;p!=min;p=next,next=next->right)addTemp(p);
    free(min);
    min=NULL;
    for(int i=0;i<=max_degree;++i)
        if(temp[i]!=NULL)addNode(temp[i]),temp[i]=NULL;
}
void decreaseKey(FibNode p,int key){
    p->key=key;
    if(p->fa==NULL){
        if(min->key>key)min=p;
    }
    else if(key<p->fa->key)cut(p);
}
/*----- Fibonacci堆 定义 END -----*/ 

/*----- Dijstra 定义 BEGIN -----*/
void addEdge(int x,int y,int l){
    Edge e=(Edge)malloc(sizeof (struct EdgeNode));
    e->v=y;
    e->l=l;
    e->next=first[x];
    first[x]=e;
}

void dijstra(){
    for(int i=1;i<=n;++i){
        if(i!=s)dis[i]=INF;
        node[i]=insert(dis[i],i);        
    }
    while(!isEmpty()){
        int x=getMin();
        deleteMin();
        for(Edge e=first[x];e!=NULL;e=e->next){
            int y=e->v;
            if(dis[x]+e->l<dis[y]){
                dis[y]=dis[x]+e->l;
                decreaseKey(node[y],dis[y]);
            }
        }
    }
}
/*----- Dijstra 定义 END -----*/

~~不写数组改写指针了，函数声明和定义分开了，终究是被大学磨平了棱角~~

~~话说c是真tm难用，没了面向对象我怎么活啊~~

斐波那契堆学习笔记

前言

抄袭来源

#define

斐波那契堆

Insert

Delete Min

Decrease Key

其他

复杂度

Insert

Delete Min

Decrease Key

优化Dijstra

代码

离散英语及其应用学习笔记