亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

結(jié)構(gòu)

斐波那契堆是由一組最小堆有序樹構(gòu)成的。每個(gè)節(jié)點(diǎn)的度數(shù)為其子節(jié)點(diǎn)的數(shù)目。樹的度數(shù)為其根節(jié)點(diǎn)的度數(shù)。

斐波那契堆中的樹都是有根的但是無序。每個(gè)節(jié)點(diǎn)x包含指向父節(jié)點(diǎn)的指針p[x]和指向任意一個(gè)子結(jié)點(diǎn)的child[x]。x的所有子節(jié)點(diǎn)都用雙向循環(huán)鏈表鏈接起來，叫做x的子鏈表。子鏈表中的每一個(gè)節(jié)點(diǎn)y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果節(jié)點(diǎn)y是x僅有的子節(jié)點(diǎn)，則left[y]=right[y]=y。

斐波那契堆中所有樹的根節(jié)點(diǎn)也用一個(gè)雙向循環(huán)鏈表鏈接起來。

使用一個(gè)指針指向斐波那契堆中最小元素。

操作

建立一個(gè)新的斐波納契堆

每個(gè)結(jié)點(diǎn)x的域

父節(jié)點(diǎn)p[x]

指向任一子女的指針child[x]——結(jié)點(diǎn)x的子女被鏈接成一個(gè)環(huán)形雙鏈表，稱為x的子女表

左兄弟left[x]

右兄弟right[x]——當(dāng)left[x] = right[x] = x時(shí)，說明x是獨(dú)子。

子女的個(gè)數(shù)degree[x]

布爾值域mark[x]——標(biāo)記是否失去了一個(gè)孩子

對(duì)于一個(gè)給定的斐波那契堆H，可以通過指向包含最小關(guān)鍵字的樹根的指針min[H]來訪問，這個(gè)結(jié)點(diǎn)被稱為斐波那契堆中的最小結(jié)點(diǎn)。如果一個(gè)斐波那契堆H是空的，則min[H] = NIL. 在一個(gè)斐波那契堆中，所有樹的根都通過left和right指針鏈接成一個(gè)環(huán)形的雙向鏈表，稱為堆的根表。于是，指針min[H]就指向根表中具有最小關(guān)鍵字的結(jié)點(diǎn)。

創(chuàng)建一個(gè)空的斐波那契堆，過程MAKE-FIB-HEAP 分配并返回一個(gè)斐波那契堆對(duì)象H；

插入一個(gè)節(jié)點(diǎn)

創(chuàng)建一個(gè)僅包含一個(gè)節(jié)點(diǎn)的新的斐波納契堆，然后執(zhí)行堆合并。

查找最小的節(jié)點(diǎn)

由于用一個(gè)指針指向了具有最小值的根節(jié)點(diǎn)，因此查找最小的節(jié)點(diǎn)是簡(jiǎn)單的操作。

合并兩個(gè)斐波納契堆

簡(jiǎn)單合并兩個(gè)斐波納契堆的根表。即把兩個(gè)斐波納契堆的所有樹的根首尾銜接并置。

釋放（刪除）最小的節(jié)點(diǎn)

分為三步：

查找最小的根節(jié)點(diǎn)并刪除它，其所有的子節(jié)點(diǎn)都加入堆的根表，即它的子樹都成為堆所包含的樹；

需要查找并維護(hù)堆的最小根節(jié)點(diǎn)，但這耗時(shí)較大。為此，同時(shí)完成堆的維護(hù)：對(duì)堆當(dāng)前包含的樹的度數(shù)從低到高，迭代執(zhí)行具有相同度數(shù)的樹的合并并實(shí)現(xiàn)最小樹化調(diào)整，使得堆包含的樹具有不同的度數(shù)。這一步使用一個(gè)數(shù)組，數(shù)組下標(biāo)為根節(jié)點(diǎn)的度數(shù)，數(shù)組的值為指向該根節(jié)點(diǎn)指針。如果發(fā)現(xiàn)具有相同度數(shù)的其他根節(jié)點(diǎn)則合并兩棵樹并維護(hù)該數(shù)組的狀態(tài)。

對(duì)當(dāng)前堆的所有根節(jié)點(diǎn)查找最小的根節(jié)點(diǎn)。

降低一個(gè)節(jié)點(diǎn)的鍵值

對(duì)一個(gè)節(jié)點(diǎn)的鍵值降低后，自鍵值降低的節(jié)點(diǎn)開始自下而上的迭代執(zhí)行下述操作，直至到根節(jié)點(diǎn)或一個(gè)未被標(biāo)記（marked）節(jié)點(diǎn)為止：

如果當(dāng)前節(jié)點(diǎn)鍵值小于其父節(jié)點(diǎn)的鍵值，則把該節(jié)點(diǎn)及其子樹摘下來作為堆的新樹的根節(jié)點(diǎn)；其原父節(jié)點(diǎn)如果是被標(biāo)記（marked）節(jié)點(diǎn)，則也被摘下來作為堆的新樹的根節(jié)點(diǎn)；如果其原父節(jié)點(diǎn)不是被標(biāo)記（marked）節(jié)點(diǎn)且不是根節(jié)點(diǎn)，則其原父節(jié)點(diǎn)被加標(biāo)記。

如果堆的新樹的根節(jié)點(diǎn)被標(biāo)記（marked），則去除該標(biāo)記。

刪除節(jié)點(diǎn)

把節(jié)點(diǎn)的鍵值調(diào)整為負(fù)無窮小，然后執(zhí)行“降低一個(gè)節(jié)點(diǎn)的鍵值”算法，然后再執(zhí)行“刪除最小節(jié)點(diǎn)”算法。

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請(qǐng)告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。