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