前言

　　斐波那契堆(Fibonacci heap)是計算機科學中最小堆有序樹的集合。它和二項式堆有類似的性質，但比二項式堆有更好的均攤時間。堆的名字來源于斐波那契數，它常用于分析運行時間。

堆結構介紹

　　基本術語介紹：

　　關鍵字：堆節點儲存的用于比較的信息

　　度數：堆節點擁有的孩子數(注意，不包括孩子的孩子)

　　左兄弟：節點左邊的兄弟節點

　　右兄弟：節點右邊的兄弟節點

　　mark:是否有孩子節點被刪除

　　斐波那契堆是一系列無序樹的集合，每棵樹是一個最小堆，滿足最小堆的性質。(注意，樹是無序的，所以不要糾結樹該怎么排序)。堆保存了堆中所有節點的數目，保存了最小關鍵字的節點(這是整個堆的唯一入口，根據這個最小節點可以獲取整個堆的任何節點)。

　　堆的節點是堆的最小單位，它是雙向鏈表的節點，意味著它保存了上下節點的信息，如下圖,(也能看出樹的根節點排列是無序的)。

　　它主要有如下性質：

　　1、關鍵字

　　2、度數

　　3、左兄弟

　　4、右兄弟

　　5、父節點

　　6、孩子節點(任一個孩子節點，隨意)

堆基本操作

　　一、插入操作

　　　　1、創建一個節點，如21

　　2、把新建的節點插入到根鏈表中，如果是最小值，則更新它為堆的最小節點。插入位置沒有規定，一般習慣插入到min的左邊。把堆的“所有節點數”值加1

　　3、插入操作完成了(插入并不會對堆進行修改，修改是在其他操作中進行的，所以比較簡單)

　　二、刪除最小節點

　　　　1、刪除最小節點，并把它的所有孩子合并到堆的根鏈表中，并更新min

　　2、合并根節點的樹，使任何樹的度(rank)不相等

　　　　觀察到7有1個孩子節點，即度為1，先保存起來，由于是初始的，肯定沒有和7度相同的

　　　　接著下一個根節點24，度為2，繼續。

　　　　23, 度為1，繼續

　　　　17, 度為1。 由于已經有度為1的根節點了，所以需要合并這兩個節點

　　　　根據最小堆得性質，把23合并到17上，作為17的孩子節點

　　　　此時17的度為2，仍然重復，繼續合并，直到沒有度一樣的根節點

　　　　最終結果如下圖

　　三、減小key值

　　　　如果沒有違背最小堆的性質，直接減小key的值

　　　　否則，把以key為根節點的樹合并到堆的根鏈表中

　　　　如果有一個節點有兩個孩子移除了，把這個節點也合并到根鏈表中，并且unmark它

　　　　現在舉一個例子來說明各種可能情況

　　　　1、不違反最小堆性質

　　　　　　把46減小為29，不違反最小堆性質，不改變堆結構

　　　　2、違反最小堆性質，合并到根鏈表中，并且unmark 它

　　　　　　把29減小為15，違反了堆性質

　　　　把15合并到根鏈表中

　　如果父節點沒有mark(沒有失去孩子), 設置它為mark

　　如果父節點已經是mark，則把父節點合并到根鏈表中，并設置為unmark。

　　把節點35減小到5　

　　由于違反了，把5合并到根

　　由于26已經mark，把26這個子樹合并到根

　　同理24合并到根

　　由于7已經是根節點了，停止，全部結束

　　四、刪除節點

　　　　刪除節點比較簡單，主要分為兩步

　　　　1、把節點值decrease比堆最小值還小

　　　　2、刪除最小值

java代碼實現(僅供參考，邏輯并不十分嚴謹)

 1 public class FibonNode<T extends Comparable<T>> { 2  3     public T key; 4      5     public FibonNode<T> child; 6      7     public FibonNode<T> left; 8      9     public FibonNode<T> right;10     11     public boolean mark;12     13     public FibonNode<T> parent;14     15     public int degree;16     17     public FibonNode(T key){18         this.degree = 0;19         this.key = key;20         this.parent = null;21         this.child = null;22         this.left = null;23         this.right = null;24         this.mark = false;25     }26 }

  1 public class FibonHeap<T extends Comparable<T>> {  2   3     PRivate int keyNum;  4   5     private FibonNode<T> min;  6   7     /*  8      * 保存當前指針  9      */ 10     private FibonNode<T> current; 11  12     /* 13      * 保存各個度對應的節點,如度為1的節點對應的節點 14      */ 15     private Map<Integer, FibonNode<T>> degreeNodes; 16  17     public FibonHeap(T key) { 18         min = new FibonNode<T>(key); 19         keyNum += 1; 20         min.left = min; 21         min.right = min; 22     } 23  24     /* 25      * 插入值 26      */ 27     public void insert(T key) { 28         FibonNode<T> node = new FibonNode<T>(key); 29         insert(node); 30     } 31  32      33     /* 34      * 刪除最小值 35      */ 36     public void deleteMin() { 37         degreeNodes = new HashMap<Integer, FibonNode<T>>(); 38         removeMinNode(); 39         consolidate(); 40  41     } 42      43     /* 44      * 刪除節點 45      */ 46     public void deleteNode(FibonNode<T> node){ 47         T everSmall = null; 48         decrease(node, everSmall); 49         deleteMin(); 50     } 51      52     /* 53      * 合并堆 54      */ 55     public FibonHeap<T> union(FibonHeap<T> heapA, FibonHeap<T> heapB){ 56         FibonNode<T> minA = heapA.min; 57         FibonNode<T> minB = heapB.min; 58         minA.right = minB; 59         minA.right.left = minB.right; 60         minB.left = minA; 61         minB.right.left = minA.right; 62         FibonNode<T> min = minA; 63         if(minB.key.compareTo(minB.key) < 0){ 64             min = minB; 65         } 66         heapA.min = min; 67         heapA.keyNum += heapB.keyNum; 68         return heapA; 69     } 70      71     private void insert(FibonNode<T> node) { 72         //插入就是直接更新左右節點就可以了 73         min.left.right = node; 74         node.left = min.left; 75         node.right = min; 76         min.left = node; 77         T minKey = min.key; 78         if (node.key.compareTo(minKey) < 0) { 79             min = node; 80         } 81         keyNum += 1; 82     } 83      84     /* 85      * 把節點從堆中刪除 86      */ 87     private void removeMinNode() { 88         FibonNode<T> left = min.left; 89         if (left == min) { 90             //說明只剩最后一個節點了，也就是最小節點自己 91             if (min.child != null) { 92                 min = null;//這里不是null，應該是孩子節點中最小節點，筆者沒有寫完而已 93             } 94         } else { 95             deleteInList(min); 96             addChToR(min); 97             min = left;    //    先隨意選個節點作為最小節點，在隨后環節會更新的 98         } 99         keyNum--;100     }101 102 103     /*104      * 把根節點合并使其所有節點的度不相等105      */106     private void consolidate() {107         current = min;108         do {109             current = putDegreeNodes(current);110             if (current.key.compareTo(min.key) < 0) {111                 min = current;112             }113             current = current.right;114         } while (current != min && current.left != current);115     }116 117     /*118      * 119      */120     private FibonNode<T> putDegreeNodes(FibonNode<T> node) {121         int nodeDegree = node.degree;122         //從map中找節點對應的度是否存在，存在說明有相同度的節點了，需要合并123         FibonNode<T> nodeInMap = degreeNodes.get(nodeDegree);    124         if (nodeInMap == null) {125             degreeNodes.put(nodeDegree, node);126         } else {127             if (node.key.compareTo(nodeInMap.key) < 0) {128                 deleteInList(nodeInMap);129                 nodeInMap.left = nodeInMap;130                 nodeInMap.right = nodeInMap;131                 node = fibLink(node, nodeInMap);132                 nodeInMap = node;133             } else {134                 deleteInList(node);135                 node.left = node;136                 node.right = node;137                 nodeInMap = fibLink(nodeInMap, node);138 139                 node = nodeInMap;140             }141             degreeNodes.put(nodeDegree, null);142             node = putDegreeNodes(node);143         }144         return node;145     }146 147     private FibonNode<T> fibLink(FibonNode<T> parent, FibonNode<T> child) {148         if (parent.child == null) {149             parent.child = child;150             151         } else {152             parent.child = insertCyle(parent.child, child);153         }154         child.parent = parent;155         parent.degree += 1;156         return parent;157     }158 159     /*160      * 從所在鏈中刪除161      */162     private void deleteInList(FibonNode<T> node) {163         FibonNode<T> left = node.left;164         FibonNode<T> right = node.right;165         left.right = right;166         right.left = left;167     }168 169     /*170      * 插入到鏈中171      */172     private FibonNode<T> insertCyle(FibonNode<T> target, FibonNode<T> node) {173         FibonNode<T> left = target.left;174         left.right = node;175         node.left = target;176         node.right = target;177         target.left = node;178         return target;179     }180 181     /*182      * 把孩子節點添加到根鏈表中183      */184     private void addChToR(FibonNode<T> node) {185         FibonNode<T> aChild = node.child;186         if (aChild == null) {187             return;188         }189         do {190             //孩子節點循環插入根191             FibonNode<T> right = aChild.right;192             min.right = insertCyle(min.right, aChild);193             aChild = right;194 195         } while (aChild != node.child);196     }197     198     public void decrease(FibonNode<T> target, T key){199         FibonNode<T> parent = target.parent;200         if(target.key.compareTo(key) < 0){201             System.out.println("只能減少key值");202             return;203         }204         if(parent == null){205             //如果修改節點是根節點，直接修改206             target.key = key;207             if(key.compareTo(min.key) < 0){208                 //更新最小節點209                 min = target;210             }211             return;212         }213         if(parent.key.compareTo(key) < 0){214             //如果值修改稿后不違反最小堆，直接修改即可215             target.key = key;216             return;217         }218         cutAndMeld(target);219         parent = cascadingCut(parent);220     }221     222     /*223      * 刪除節點，并合并到根中224      */225     private void cutAndMeld(FibonNode<T> target){226         target.parent = null;227         target.mark = false;228         insert(target);229     }230     231     /*232      * 級聯刪除，使其符合斐波那契堆性質233      */234     private FibonNode<T> cascadingCut(FibonNode<T> parent){235         if(null == parent){236             return null;237         }238         parent.degree--;239         if(parent.mark == false){240             parent.mark = true;241         }else{242             cutAndMeld(parent);243             parent = cascadingCut(parent);244         }245         return parent;246     }247     248     249 }

參考文獻

　　http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm

　　斐波那契堆(一)之 圖文解析 和 C語言的實現

　　fibonacci-heap

　　Fibonacci_heap