你的位置:首页 > 软件开发 > Java > 斐波那契堆(Fibonacci heap)原理详解(附java代码实现)

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

发布时间:2015-06-06 12:02:03
前言  斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质,但比二项式堆有更好的均摊时间。堆的名字来源于斐波那契数,它常用于分析运行时间。 堆结构介绍  基本术语介绍:  关键字:堆节点储存的用于比 ...

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

前言

  斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质,但比二项式堆有更好的均摊时间。堆的名字来源于斐波那契数,它常用于分析运行时间。

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

 

 

堆结构介绍

  基本术语介绍:

  关键字:堆节点储存的用于比较的信息

  度数:堆节点拥有的孩子数(注意,不包括孩子的孩子)

  左兄弟:节点左边的兄弟节点

  右兄弟:节点右边的兄弟节点

  mark:是否有孩子节点被删除

 

  斐波那契堆是一系列无序树的集合,每棵树是一个最小堆,满足最小堆的性质。(注意,树是无序的,所以不要纠结树该怎么排序)。堆保存了堆中所有节点的数目,保存了最小关键字的节点(这是整个堆的唯一入口,根据这个最小节点可以获取整个堆的任何节点)。

  堆的节点是堆的最小单位,它是双向链表的节点,意味着它保存了上下节点的信息,如下图,(也能看出树的根节点排列是无序的)。

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

  它主要有如下性质:

  1、关键字

  2、度数

  3、左兄弟

  4、右兄弟

  5、父节点

  6、孩子节点(任一个孩子节点,随意)

 

堆基本操作

  一、插入操作

    1、创建一个节点,如21

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

  2、把新建的节点插入到根链表中,如果是最小值,则更新它为堆的最小节点。插入位置没有规定,一般习惯插入到min的左边。把堆的“所有节点数”值加1

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

  3、插入操作完成了(插入并不会对堆进行修改,修改是在其他操作中进行的,所以比较简单)

 

  二、删除最小节点

    1、删除最小节点,并把它的所有孩子合并到堆的根链表中,并更新min

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

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

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

  2、合并根节点的树,使任何树的度(rank)不相等

    观察到7有1个孩子节点,即度为1,先保存起来,由于是初始的,肯定没有和7度相同的

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

    接着下一个根节点24,度为2,继续。

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

    23, 度为1,继续

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

    17, 度为1。 由于已经有度为1的根节点了,所以需要合并这两个节点

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

    根据最小堆得性质,把23合并到17上,作为17的孩子节点

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

    此时17的度为2,仍然重复,继续合并,直到没有度一样的根节点

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

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

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

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

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

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

    最终结果如下图

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

 

    

 

  三、减小key值

    如果没有违背最小堆的性质,直接减小key的值

    否则,把以key为根节点的树合并到堆的根链表中

    如果有一个节点有两个孩子移除了,把这个节点也合并到根链表中,并且unmark它

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

    现在举一个例子来说明各种可能情况

    1、不违反最小堆性质

      把46减小为29,不违反最小堆性质,不改变堆结构

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

    2、违反最小堆性质,合并到根链表中,并且unmark 它

      把29减小为15,违反了堆性质

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

    把15合并到根链表中

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

  如果父节点没有mark(没有失去孩子), 设置它为mark

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

  如果父节点已经是mark,则把父节点合并到根链表中,并设置为unmark。

  把节点35减小到5 

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

  由于违反了,把5合并到根

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

  由于26已经mark,把26这个子树合并到根

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

  同理24合并到根

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

  由于7已经是根节点了,停止,全部结束

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

  四、删除节点

    删除节点比较简单,主要分为两步

    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 }

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

关键词:JAVA

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。