斐波那契堆.docx

斐波那契堆
―、堆的结构
堆中各个有序树的树根之间用双向循环链表连接。每颗有序树中兄弟节点之间用双向循环链 表连接。
每个节点拥有fa，child，last，next四个指针：分别指向父节点、任意一个子节点、左右相 邻的兄弟节点。
ld
#define r(x) heap[x].next
#define l(x) heap[x].last
#define mark(x) heap[x].mark
typedef long long ll;
using namespace std;
const int mx = 1000000;
int v[mx];
int p, n, m;
struct Fibonacci_Heap
{
int du, fa, child, next, last, mark;
} heap[mx];
vector<int> a[25]; ///桶
ll d[mx]; ///距离数组
int head[mx], cnt;
struct N
{
int from, to, w, next;
} edge[mx];
///链式前向星(用数组模拟的邻接链表)
void add(int from, int to, int w)
{
edge[cnt]. to = to;
edge[cnt]. from = from;
edge[cnt]. w = w;
edge[cnt]. next = head[from];
head[from] = cnt++;
}
///向邻接链表中添加一条由from到to的边，且权重为w
void Link(int x, int y)
{
if(!x||!y) return;
l (r (x))=l (y), r (l (y))=r (x);
r (x)=y, l(y)=x;
}
///此方法将x点与y点相连
void Cut(int x)
{
if (ch (fa(x))==x) ch (fa(x))=r (x)==x?0: r (x);
du (fa(x))--;
r (l(x))=r (x), l(r(x))=l (x);
l (x)=r (x)=x;
fa(x)=mark(x)=0;
}
///次方法将x点从堆中切除
void Insert(int x)
{
l (x)=r (x)=x, v[x] = 1;
Link(x, p);
if(d[x]<d[p]) p=x;
}
///将点x插入到堆中
void Decrease(int x)
{
if(!fa(x))
{
if(d[x]<d[p]) p=x;
return;
}
if(d[x]>=d[fa(x)]) return;
do
{
int y=fa(x);
Cut (x), Link(p, x);
if(d[x]<d[p]) p=x;
x=y;
}
while (mark(x));
if (fa(x)) mark(x)=1;
///将x点从堆中去除。
void Extract ()
{
int i, j, x, y;
for (i=r (p); i!=p; i=r(i))
a[du(i)]. pus