斐波那契堆(Fibonacci heap)原理详解(附java代码实现)

前言

　　斐波那契堆(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