1. 結(jié)構(gòu)

斐波那契堆是一系列具有最小堆序的有根樹的集合, 同一代(層)結(jié)點由雙向循環(huán)鏈表鏈接, 為了便于刪除最小結(jié)點, 還需要維持鏈表為升序, 即nd<=nd.right(nd==nd.right時只有一個結(jié)點或為 None), 父子之間都有指向?qū)Ψ降闹羔?

結(jié)點有degree 屬性, 記錄孩子的個數(shù), mark 屬性用來標(biāo)記(為了滿足勢函數(shù), 達(dá)到攤還需求的)

還有一個最小值指針 H.min 指向最小根結(jié)點

2. 勢函數(shù)

下面用勢函數(shù)來分析攤還代價, 如果你不明白, 可以看攤還分析

t 是根鏈表中樹的數(shù)目,m(H) 表示被標(biāo)記的結(jié)點數(shù)

最初沒有結(jié)點

3. 最大度數(shù)

結(jié)點的最大度數(shù)(即孩子數(shù)), 證明放在最后

4. 操作

4.1. 創(chuàng)建一個斐波那契堆

4.2. 插入一個結(jié)點

nd = new node
nd.prt = nd.chd = None
if H.min is None:
    creat H with nd
    H.min = nd
else:
    insert nd into  H's root list
    if H.min<nd: H.min = nd
H.n +=1

攤還代價為

4.3. 尋找最小結(jié)點

直接用 H.min,

4.4. 合并兩個斐波那契堆

def union(H1,H2):
    if H1.min ==None or (H1.min and H2.min and H1.min>H2.min):
        H1.min = H2.min
    link H2.rootList to H1.rootList 
    return H1

易知

4.5. 抽取最小值

抽取最小值, 一定是在根結(jié)點, 然后將此根結(jié)點的所有子樹的根放在 根結(jié)點雙向循環(huán)鏈表中, 之后還要進行樹的合并. 以使每個根結(jié)點的度不同,

def extract-min(H):
    z = H.min
    if z!=None:
        for chd of z:
            link chd to H.rootList
            chd.prt = None
        remove z from the rootList of H
        if z==z.right:
            H.min = None
        else:
            H.min = z.right
            consolidate(H)
        H.n -=1
    return z

consolidate 函數(shù)使用一個 輔助數(shù)組degree來記錄所有根結(jié)點(不超過lgn)對應(yīng)的度數(shù), degree[i] = nd 表示.有且只有一個結(jié)點 nd 的度數(shù)為 i.

def consolidate(H):
    initialize degree  with None
    for nd in H.rootList:
        d = nd.degree
        while degree[d] !=None:
            nd2 = degree[d]
            if nd2.degree < nd.degree:
                nd2,nd = nd,nd2

            make nd2 child of nd  
            nd.degree = d+1
            nd.mark = False # to balace the potential 

            remove nd2 from H.rootList
            degree[d] = None
            d+=1
        else: degree[d] = nd
    for i in degree:
        if i!=None: 
            link i to H.rootList
            if H.min ==None: H.min = i
            else if H.min>i: H.min = i

時間復(fù)雜度為 即數(shù)組移動的長度, 而最多有 lgn個元素

4.6. 關(guān)鍵字減值

def decrease-key(H,x,k):
    if k>x.key: error 
    x.key = k
    y=x.p
    if y!=None and x.key < y.key:
        cut(H,x,y)
        cascading-cut(H,y)
    if x.key < H.min.key:
      H.min = x
def cut(H,x,y):
    remove x from the child list of y, decrementing y.degree
    add x to H.rootList
    x.prt = None
     x.mark = False

def cascading-cut(H,y):
    z- y,prt
    if z !=None:
        if y.mark ==False:y.mark = True
        else:
            cut(H,y,z)
            cascading-cut(H,z)

4.7. 刪除結(jié)點

decrease(H,nd, MIN)
extract-min(H)

最大度數(shù)的證明

這也是斐波那契這個名字的由來,