你的位置:首页 > Java教程

[Java教程]斐波那契堆(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