二項(xiàng)堆與斐波那契堆

1、理想王國(guó)的數(shù)據(jù)結(jié)構(gòu) 二項(xiàng)堆與斐波那契堆 Binomial Heap #define du(x) heapx.du #define fa(x) heapx.fa #define ch(x) heapx.child #define r(x) heapx.next #define l(x) heapx.last #define mark(x) heapx.mark heapu; vector a25; /桶 _int64 du; /距離數(shù)組 代碼實(shí)現(xiàn) 雙向循環(huán)鏈表操作 inline void Link(int x,int y) if(!x|!y) return; l(r(x)=l(y),r(l(y)

2、=r(x); r(x)=y,l(y)=x; inline 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; 代碼實(shí)現(xiàn) 插入與更新 void Insert(int x) l(x)=r(x)=x,vx=1; Link(x,p); if(dxdp) p=x; void Decrease(int x) if(!fa(x) if(dx=dfa(x) return; do int y=fa(x); Cut(x),Li

3、nk(p,x); if(dxdp) p=x; x=y; while(mark(x); if(fa(x) mark(x)=1; 代碼實(shí)現(xiàn) 抽取最小節(jié)點(diǎn) void Extract() int i,j,x,y; for(i=r(p);i!=p;i=r(i) adu(i).push_back(i); if(i=ch(p) adu(i).push_back(i); for(i=r(i);i!=ch(p);i=r(i) adu(i).push_back(i); for(p=i=0;i=0;j-) if(j) x=aij,y=ai-j; if(dydx) swap(x,y); l(y)=r(y)=y; Li

4、nk(ch(x),y); ch(x)=y,fa(y)=x,du(x)+; ai+1.push_back(x); else x=aij,l(x)=r(x)=x,fa(x)=mark(x)=0; Link(p,x); if(dxdp) p=x; ai.clear(); 代碼實(shí)現(xiàn) Dijkstra void Fibonacci_Heap_Dijkstra() memset(d,0 x7f,sizeof(d); d1=0; Insert(1); for(int t=1;tdx+edgei) dy=dx+edgei; if(vy) Decrease(y); else Insert(y); 參考文獻(xiàn) 維基百科二項(xiàng)堆詞條 百度文庫(kù)FibHeaps背景與分析 The End 感謝CCF給予我們展示和交流的平臺(tái)。 感謝衡陽(yáng)八中鄒毅老師(bzoj-root)推薦斐波那契堆相關(guān)論文資料。 感謝 唐山一中石昊悅 (This_poet)、石家莊一中孫嘉裕 (sjynoi) 審閱全稿；石家莊二中劉炎明 (Riatre) 提供數(shù)據(jù)構(gòu)造思路；石家莊 二中