GMS资讯网 > 信息

斐波那契堆（三）Java实现

2023-10-07 15:35

总结

斐波那契堆分别通过C和C++实现。本章给出了斐波那契堆的 Java 版本。老话说，三种实现的原理是一样的，选其一就明白了。

内容
1.斐波那契堆简介
2。斐波那契堆的基本操作
3.斐波那契堆的Java实现（完整源代码）
4 .斐波那契堆的 Java 测试程序

转载请注明出处：

更多内容：数据结构与算法系列目录

？（03）斐波那契堆的Java实现（3）

斐波那契堆简介

斐波那契堆是可合并堆，可用于实现合并优先级队列。它比二项式堆具有更好的摊余分析性能，其合并操作的时间复杂度为O(1)。
和二项式堆一样，它也是由一组堆最小有序树组成，是一个可合并堆。
与二项式堆的区别在于，斐波那契堆中的树不一定是二项式树；而二项式堆中的树是有序的，而斐波那契堆中的树都是有根且无序的。

斐波那契堆的基本操作

1。基本定义

公共 类 FibHeap {

    私有 int keyNum; //堆中节点总数私有 FibNode 最小值； //最小节点（某个最小堆的根节点）

    私有 类 FibNode {
        int键； //关键字（键值）
        int度； //度
        FibNode 左； //左兄弟
        FibNode 右； //右弟
        FibNode 子节点； // 第一个子节点
        FibNode 父级； //父节点
        布尔值标记； //第一个孩子被删除了吗

        public FibNode(int key) {
            这个.key =键；
            这个.度= 0；
            这个.标记=假；
            这个.左 = 这个；
            这个.right = 这个；
            这个.parent = null;这个.child = null；
        }
    }

    ...
}

FibNode是斐波那契堆的节点类，包含更多信息。 key用于比较节点的大小， Degree记录该节点的度数，left和right分别指向该节点的左右兄弟，child为该节点的第一个子节点，parent为该节点的父节点，marked记录该节点是否被标记。删除第一个子节点（标记在删除节点时很有用）。
FibHeap是斐波那契堆对应的类。 min是保存当前堆的最小节点，keyNum用于记录堆中节点总数，maxDegree用于记录堆中最大度数，cons用于临时保存堆数据的临时空间删除节点时。

以上是斐波那契堆的两种不同结构图的比较。由此可以看出，斐波那契堆是由一组最小堆组成的，这些最小堆的根节点组成了一个双向链表（以下简称“根链表”）；斐波那契堆中最小的节点就是“根链表中的最小节点”！

PS。上图结构与测试代码中“基本信息”测试函数的结果一致；您可以通过测试程序自行验证！

2。插入操作

插入操作非常简单：向堆中插入一个节点，将该节点直接插入到“根链表的最小节点”之前；如果插入的节点小于“最小节点”，则更新“最小节点”以插入该节点。

上图为插入操作示意图。

斐波那契堆的根链表是一个“双向链表”，这里将min节点视为双向链表的表头（后面也是如此）。插入节点时，每次都是“将该节点插入到最小节点之前（即插入到双向链表的末尾）”。另外，对于根链表中最小堆只有一个节点的情况，插入操作很容易演变为双向链表的插入操作。

另外，插入操作图对应测试程序中的“插入操作”，有兴趣的可以亲自验证一下。

插入操作代码

/*
 * 在根节点之前添加节点堆节点（循环链表中）
 *一个根
 * 一个……节点……根
*/
private void addNode(FibNode 节点, FibNode 根) {
    节点.left = root.left;
    root.left.right =节点；
    node.right =根；
    root.left =节点；
}
 
/*
 * 将node节点插入斐波那契堆
 */
私有 void插入（FibNode节点）{
    if（keyNum == 0）
        最小 = 节点；
    否则 {
        添加节点（节点，最小值）；
        if（node.key < min.key）
            最小 = 节点；
    }

    keyNum++;
}
 
/*
 * 以键值key创建一个新节点并将其插入到斐波那契堆中*/
公共 void插入（int键）{
    FibNode节点；

    节点 = new FibNode(key);
    if（节点==null）
        返回；

    插入（节点）；
}

3。合并操作

合并操作和插入操作的原理很相似：只是将一个堆的根链表插入到另一个堆的根链表中。简单来说就是两个双向链表拼接成一个双向链表。

上图是合并操作的示意图。这个操作图对应的是测试程序中的“合并操作”！

合并操作代码

/*
* 将双向链表b链接到双向链表a的后面
*/
private void catList(FibNode a, FibNode b) {
    FibNode tmp；

    tmp = a.右；
    a.右= b.右；
    b.右.左= a;
    b.右= tmp;
    tmp.left = b;
}

/*
 * 将其他的合并到当前堆中
 */publicvoid联合（FibHeap其他）{
    if（其他==null）
        返回；

    if((这个.min)==null){ // 这个没有“最小节点”
        这个.min =其他.min;
        这个.keyNum = other.keyNum;
        其他=空；
    } else if((other.min) == null) { // 这个有“最小节点”&& 其他没有《最小节点》
        其他 = null；
    } else { // 这个有“最小节点” && 其他有“最小节点”
        // 将“其他根列表”添加到“此”
    catList(这个.min, other.min);

        if (这个.min.key > other.min.key)
            这个.min =其他.min;
        这个.keyNum += other.keyNum;
        其他=空;;
    }}

4。取出最小节点

提取最小节点的操作是斐波那契堆中比较复杂的操作。
(1) 将要提取的子树直接与根表中的最小节点连接起来；
(2) 合并所有度数相等的树，直到没有度数相等的树为止。

上图是提取最小节点的示意图。图片应该非常清晰。如果有任何疑问，请查看代码。

另外，这个操作图对应的是测试程序中的“删除最小节点”！有兴趣的可以自己验证一下。

取出最小节点代码

/*
 * 将节点链接到根节点
 */
private void 链接（FibNode 节点，FibNode 根）{
    //从双向链表中删除节点
 移除Node(节点);
    // 将节点设置为根 的子节点
    if（root.child == null）
        root.child =节点；
    否则
        addNode(节点, root.child);

    node.parent =根；
    根.度++;
    节点.标记=false;
}
 
/*
 * 合并斐波那契堆根列表中同度左右树
 */私人void巩固（）{
// 计算log2(keyNum)，floor表示向上取整！
// 前。 log2(13) = 3，向上舍入为 4。
    354int maxDegree = (int) Math.floor(Math.log(keyNum) / Math.log(2.0) ) );
    int D = maxDegree + 1；
    FibNode[] cons = new FibNode[D+1];

    对于 (int i = 0; i < D; i++)
        cons[i] = null；
 
    // 合并度数相同的根节点，使每个度数的树都唯一
    同时（分钟！=空）{
        FibNode x = extractMin(); //取出堆中最小树（最小节点所在树）
        int d = x.度； // 获取最小树的度数
        // cons[d] != null，这意味着有两棵树（x 和 y）具有相同的“度”。 
        同时 (cons[d] != null) {
            FibNode y = cons[d]; // y 是“与 x 具有相同度数的树”if (x.key > y.key) { //确保x的key值小于y
                FibNode tmp = x;
                x = y；
                y = tmp；
            }

            链接（y，x）； // 将 y 链接到 x
            cons[d] = null；
            d++；
        }
        缺点[d] = x;
    }
    分钟=空；
 
    //将cons中的节点重新添加到根表
    对于 (int i=0; i) {

        if (cons[i] != null) {
            if（最小值 == null）
                最小 = cons[i];
            否则 {
                addNode(cons[i], 分钟);
                if ((cons[i]).key < min.key)
                    最小 = cons[i];
            }
        }
    }
}
 
/*
 * 删除最小的节点
 */
publicvoidremoveMin() {if（分钟==null）
        返回；

    FibNode m = 分钟；
    //将min的每个儿子（儿子和儿子的兄弟）添加到“斐波那契堆的根列表”
    while (m.child != null) {
        FibNode 子节点 = m.child;

        删除节点（子节点）；
        if（child.right ==孩子）
            m.child = null；
        否则
            m.child = child.right;

        添加节点（子节点，最小值）；
        child.parent = null；
    }

    // 从根列表中删除 m
 移除Node(m);
    // 如果m是堆中唯一的节点，则将堆的最小节点设置为null；
    // 否则，将堆的最小节点设置为非空节点（m.right），然后进行调整。 
    if（米.右==米）
        分钟=空；
    否则 {
        分钟 = 米.右；
        合并（）；
    }
    keyNum--；

    m = 空；
}

5。减少节点值

减少斐波那契堆中节点的键值。这个操作的难点在于：如果减少节点后“最小堆”属性被破坏了，如何维护呢？现将一般情况分析如下。
(1)首先将“缩减节点”从“所在最小堆”中分离出来；然后将“节点”关联到“根链表”。如果被减少的节点不是单个节点，而是包含子树的根。然后从“最小堆”中剥离以“缩减节点”为根的子树，然后将该树与根链表关联起来。
(2)接下来，对“缩减节点”的原始父节点进行“级联切割”。所谓“级联剪切”是指被约简的节点破坏最小堆性质并被截断后，从“其父节点”开始进行递归级联剪切操作。
级联操作的具体动作是：如果父节点（缩减节点的父节点）的mark标记为false，则设置为true，然后退出。父否则，将父节点从最小堆（方法与“切割节点的方法”相同）；然后递归地“切割”祖父节点。
标记mark的作用是标记“本节点的子节点是否已被删除”，其作用是实现级联剪切。级联剪切的真正目的是防止“最小堆”从二叉树演变成链表。
(3) 最后，不要忘记更新根列表的最小节点。

上图是减少节点值的示意图。这个运行图对应的是测试程序中的“reduce节点”！

减少节点值的代码

/*
 * 修改学位
 */
private void renewDegree（FibNode 父级，int）度）{Parent.level -= 度；
    if（父.父！= null）
        renewDegree(parent.parent, 学位);
}
 
/*
 * 从父节点parent的子链接中剥离节点，
 * 并使节点成为“堆根链表”的成员。
 */
private void cut(FibNode 节点, FibNode 父节点) {
    删除节点（节点）；
    renewDegree(父节点, 节点.度);
    //节点没有兄弟
    if（节点==节点.right）
        Parent.child = null；
    否则
        Parent.child = 节点.right;

    节点.parent = null;
    节点.左=节点.右=节点;
    节点.标记=false;
    // 将“节点所在树”添加到“根链表”中
 addNode(node, min);
}

/*
 * 对node节点进行“级联切割”
 *
 * 级联剪切：如果减少的节点破坏了最小堆属性，
 * 然后将其剪切（即从双向链表中删除并替换为
 * 插入到最小树根节点构成的双向链表中），
 * 然后从“待剪节点的父节点”到树的根节点递归地进行级联剪枝。
 */private void cascadingCut(FibNode 节点) {
    FibNode父节点=node.parent;

    if（父级！= null）{
        if (node.marked == false)
            节点.标记=true;
        否则 {
            剪切（节点，父节点）；
            级联剪切（父级）；
        }
    }
}

/*
 * 将斐波那契堆中节点node的值减少为key
 */
 -privatevoid降低（fibnode node，int键）{
    if（最小值==null ||节点==null）
        返回；

    if（键>节点.key）{
    System.out.printf("减少失败：新key(%d)不小于当前key(%d)\n", key, node.key);
        返回；
    }

    FibNode父节点=node.parent;
    node.key =键；if (父！=null && (node.key <parent.key)) {
        // 将节点从父节点parent中拆分出来，并将该节点添加到根链表中
 cut（节点，父节点）；
        级联剪切（父级）；
    }

    //更新最小节点
    if（node.key < min.key）
        最小 = 节点；
}

6。增加节点值

增加节点值与减少节点值类似。这个操作的难点还在于如何保持“最小堆”性质。思路如下：
（1）将“添加节点”的“左孩子及其所有兄弟”链接到根链表。
(2)接下来，将“添加的节点”添加到根链表中；但不要忘记级联切割它。

上图是增加节点值的示意图。这个运行图对应的是测试程序中的“增加节点”！

增加节点值的代码

/*
 * 增加斐波那契堆中节点node的值作为key
 */
 -privatevoid升高（fibnode node，int键）{
    if（最小值==null ||节点==null）
        返回；if ( key <= 节点.key) {
    System.out.printf("增加失败：新key(%d)不大于当前key(%d)\n", key, node.key);
        返回；
    }

    // 将节点的每个儿子（不包括孙子、曾孙...）添加到“斐波那契堆的根列表”
    while (node.child != null) {
        FibNode子节点=node.child;
        删除节点（子节点）； // 从节点的子节点列表中删除子节点
        if（子项.right ==子项）
            节点.child = null;
        否则
            node.child = child.right;

        添加节点（子节点，最小值）； // 将子节点添加到根链表
        child.parent = null；
    }
    节点.度= 0;
    node.key =键；

    // 如果节点不在根链表中，
    // 将从父节点parent的子链接中剥离该节点。
    //并使节点成为“堆根链表”的成员，
    // 然后进行“层叠切割”// 否则，判断堆的最小节点是否需要更新
    FibNode父=node.parent;
    if（父！= null）{
        剪切（节点，父节点）；
        级联剪切（父级）；
    } else if（分钟==节点）{
        FibNode右=node.right;
        同时（右！=节点）{
            if(node.key > right.key)
                分钟=右；
            右=右.右;
        }
    }
}

7。删除节点

为了删除节点，本文使用了“删除最小节点”和“减少节点值”的组合操作。
(1) 首先减少被删除节点的key值。减小后的值可以大于“原来的最小节点值”。
(2) 然后，取出最小的节点即可。

删除节点值的代码

/*
 * 删除节点节点
 */
private void 删除（FibNode 节点）{
    int m = 最小键；
    减少（节点，m-1）；
    删除Min();
}

注：斐波那契堆的“更新”、“打印”、“销毁”等接口不再单独介绍。他们的实现代码在下面的源代码中给出，请RTFSC（Read The Fucking Source Code）！

斐波那契堆的Java实现（完整源码）

斐波那契堆实现文件（m.gsm-guard.net）

 1 /**
 2  * Java 语言：斐波那契堆
 3  *
 4  * @author skywang
 5  * @日期 2014/04/07
 6 */
 7
 8 公共 类 FibHeap {
 9
 10 私有 int keyNum; //堆中节点总数
 11 私有 FibNode 最小值； //最小节点（某个最小堆的根节点）
 12
 13 私有 类 FibNode { 14 int键； //关键字（键值）
 15 int 度； //度
 16 FibNode 左； //左兄弟
 17 FibNode 右； //右弟
 18 FibNode 子节点； // 第一个子节点
 19 FibNode 父级； //父节点
 20 boolean 已标记； //删除了吗？一个孩子
 21
 22 公共 FibNode（int键）{
 23这个.key =键；
 24 这个.度 = 0；
 25这个.标记=假;
 26这个.左=这个; 27这个.右 = 这个;
 28 这个.parent = null；
 29 这个.child = null；
 30  }
 31  }
 32
 33 public FibHeap() {
 34 这个.keyNum = 0；
 35 这个.min = null；
 36  }
 37
 38 /*
 39  * 将节点从双链表移除
 40 */
41privateVoidVoidremovenode（fibnode node）{
 42节点.左.右=节点.右;
 43节点.right.left =节点.left;
 44  }
 45
 46 /*
 47  * 将节点堆结点加入根结点之前(循环链表中) 48  * 一个……根
 49  * 一个……节点……根
 50 */
 51 私有 void addNode(FibNode 节点, Fi b节点根) {
 52 节点.left = 根.left;
 53 root.left.right = 节点；
 54节点.right =根；
 55 root.left = 节点；
 56  }
 57
 58 /*
 59  * 将节点节点插入到斐波那契堆中
 60 */
 61 私有 void插入（FibNode节点）{
 62 if（keyNum == 0）
 63最小值=节点；
 64 其他 {
 65  addNode(node, min);
 66 if（node.key < min.key） 67最小值=节点；
 68  }
 69
 70 keyNum++；
 71  }
 72
 73 /*
 74  * 以键值key创建一个新节点，插入到斐波那契堆中
 75 */
 76 公共 void 插入（） int键）{
 77  FibNode 节点；
 78
 79 节点 = 新 FibNode(key);
 80 if（节点== null）
 81 返回 ;
 82
 83  插入（节点）；
 84  }
 85
 86 /*
 87  * 将双向链表 b 链接到双向链表 a 的后面
 88 */
 89 私有 void catList(FibNode a, Fi b节点 b) { 90  FibNode tmp；
 91
 92 tmp = a.右；
 93 a.右 = b.右；
 94 b.右.左= a;
 95 b.right = tmp;
 96 tmp.left = b;
 97  }
 98
 99 /*
100  * 将其他合并到当前堆中
101 */
102 public void union（FibHeap 其他）{
103if（其他==null）
104返回;
105
106 if((这个.min) == null) { // 这个没有“最小节点”
107 这个.min =其他.min;
108 这个.keyNum = other.keyNum;
109其他=空；110 } else if((other.min) == null ) { // 这有“最小节点”&&其他没有“最小节点”
111其他=null；
112 } else { // 这个有“最小节点” && 其他有“最小节点”
113 // 将“其他根列表”添加到“此”
114 catList(这个.min, other.min);
115
116 if (这个.min.key > other.min.key)
117 这个.min =其他.min;
118 这个.keyNum += other.keyNum;
119其他 = 空;;
120  }
121  }
122
123 /*
124  * 从根链表中移除“堆的最小节点”，
125  * 这意味着“从堆中移除最小节点所属的树”！
126 */
127 private FibNode extractMin() {
128 FibNode p = 最小值；
129130 if（p == p.右）
131分钟=空；
132 其他 {
133  移除Node(p);
134 分钟 = 右；
135  }
136 p.左 = p.右 = p；
137
138 返回 p;
139  }
140
141 /*
142  * 将节点链接到根节点
143 */
144 private void 链接（FibNode 节点，FibNode 根）{
145 // 从双向链表中删除节点
146  移除Node(节点);
147 // 将节点设置为根的子节点
148 if（root.child == null）
149 root.child = 节点；
150 其他
151  addNode(node, root.child);
152
153node.parent =根；
154根.度++;
155节点.marked = false；
156  }157
158 /*
159  * 合并斐波那契堆根列表中同度的左右树
160 */
161私人void巩固（）{
162 // 计算log2(keyNum)，floor表示向上取整！
163 // 例如。 log2(13) = 3，向上舍入为 4。
164 int maxDegree = (int) Math.floor(Math.log(keyNum) / Math.log(2.0) ））；
165 int D = maxDegree + 1；
166 FibNode[] cons = 新 FibNode[D+1];
167
对于 (INT I = 0; I )
169 cons[i] = null；
170
171 // 合并度数相同的根节点，使每个度数的树唯一
172 同时（分钟！= null）{
173 FibNode x = extractMin(); //取出堆中的最小树（最小节点所在的树）
174 int d = x.度； // 获取最小树的度数175 // cons[d] != null，这意味着有两棵树（x 和 y）具有相同的“度”。 
176 同时 (cons[d] != null) {
177 FibNode y = cons[d]; // y 是“与 x 具有相同度数的树”
178 if (x.key > y.key) { // 确保 x 的键值小于 y 
179 FibNode tmp = x;
180 x = y；
181 y = tmp;
182  }
183
184链接（y，x）； // 将 y 链接到 x 
185 缺点[d] = 空；
186d++；
187  }
188 cons[d] = x；
189  }
190分钟=空；
191
192 // 将cons中的节点重新添加到根表
For (INT i = 0; I ) {
194
195 if (cons[i] != null) {196 if（最小值 == null）
197 min = cons[i];
198 其他 {
199  addNode(cons[i], min);
200 if ((cons[i]).key < min.key)
201 min = cons[i];
202  }
203  }
204  }
205  }
206
207 /*
208  * 删除最小节点
209*/
210 public voidremoveMin() {
211 if（最小值==null）
212 返回 ;
213
214 FibNode m = 分钟；
215 //将每一个儿子（儿子和儿子的兄弟）都添加到“斐波那契堆的根链表”中
216 while (m.child != null) {
217 FibNode 子节点 = m.child;
218
219  移除Node(子节点);220 if（child.right == 孩子）
221 m.child = null；
222 其他
223 m.child = child.right;
224
225  addNode(child, min);
226 child.parent = null;
227  }
228
229 //从根列表中删除m
230  移除节点(m);
231 // 如果m是堆中唯一的节点，则将堆的最小节点设置为null；
232 // 否则，将堆的最小节点设置为非空节点（m.right），然后进行调整。 
233 if（米右 == 米）
234分钟=空；
235 其他 {
236分钟=米.右；
237  巩固();
238}
239 keyNum--；
240
241 m = null；
242  }
243
244 /*
245  * 获取斐波那契堆中最小键值；失败时返回-1
246 */247 公共 int 最小值（）{
248 if（分钟==null）
249 返回 -1；
250
251 返回分钟键；
252  }
253
254 /*
修改  * 度数
256 */
257 private void renewDegree（FibNode 父级，int 度）{
258父母.学位-=学位;
259 if（父.父！= null）
260  renewDegree(parent.parent, Degree);
261  }
262
263 /*
264  * 将节点从父节点父节点的子链接中分割出来，
265  * 净化节点成为“堆的根链表”中的一员。
266 */
267 private void cut（FibNode 节点，FibNode 父节点）{
268  移除Node(节点);
269  renewDegree(parent, node. Degree);270 //节点没有兄弟
271 if（节点==节点.right）
272父.子=null;
273 其他
274parent.child =node.right;
275
276节点.parent = null;
277 节点.left = 节点.right = 节点；
278 节点.marked = false；
279 // 将“节点所在树”添加到“根链表”中 
280  addNode(node, min);
281  }
282
283 /*
284  * 在node节点上进行“级联剪切”
285  *
286  * 级联剪切：如果减少的节点破坏了最小堆属性，
287  * 然后剪切（即从双向链表中删除，替换为
288  *插入到最小树根节点构成的双向链表中），
289  * 然后从“待剪节点的父节点”到树的根节点递归地进行级联剪枝。
290 */
291 private void cascadingCut（FibNode 节点）{
292 FibNode 父节点 = node.parent;
293294 if（父！= null）{
295 if（节点.marked == false）
296 节点.marked = true；
297 其他 {
298  剪切（节点，父节点）；
299  级联剪切（父级）；
300  }
301  }
302  }
303
304 /*
305  * 将斐波那契堆中节点的值减少到key
306 */
307 private void减少（FibNode节点，int 键）{
308 if（分钟==null ||节点==null ）
309 返回 ;
310
311 if（key > 节点.key）{
312 System.out.printf("减少失败：新key(%d)不小于当前key(%d)\n", key, node.key);
313 返回 ;
314  }
315316 FibNode 父节点 = node.parent;
317node.key =键；
318 if（父级！=null &&（node.key <父级。关键））{
319 // 将节点从父节点parent中拆分出来，并将该节点添加到根链表中
320  剪切（节点，父节点）；
321  级联剪切（父级）；
322  }
323
324 // 更新最小节点
325 if（node.key < min.key）
326 min =节点；
327  }
328
329 /*
330  * 增加斐波那契堆中节点node的值作为key
331 */
332 private void增加（FibNode节点，int 键）{
333 if (min==null ||node==null ）
334 返回 ;
335
336 if ( key <= 节点.key) {337 System.out.printf("增加失败：新key(%d)不大于当前key(%d)\n", key, node.key);
338 返回 ;
339  }
340
341 // 将节点的每个儿子（不包括孙子、曾孙...）添加到“斐波那契堆的根列表”
342 while (node.child != null) {
343 FibNode 子节点 = node.child;
344 移除Node(子节点); //从节点的子节点列表中删除子节点
345 if（child.right == 孩子）
346node.child = null;
347 其他
348node.child =child.right;
349
350 addNode(child, min); // 将子节点添加到根链表
351 child.parent = null；
352  }
353 节点.度 = 0;
354node.key =键；
355356 // 如果节点不在根列表中，
357 // 将从父节点的子链接中剥离该节点，
358 //并使节点成为“堆根列表”的成员，
359 // 然后进行“层叠切割”
360 // 否则，判断堆的最小节点是否需要更新
361 FibNode 父节点 = node.parent;
362 if（父！= null）{
363  剪切（节点，父节点）；
364  级联剪切（父级）；
365 } else if（分钟==节点）{
366 FibNode 右 = 节点.right;
367 同时（右！=节点）{
368 if（node.key > right.key）
369分钟=右；
370右=右.右；
371  }
372  }
373  }
374
375 /*
376  * 将斐波那契堆的node节点的key值更新为key
377 */399 FibNode t = 根； //临时节点
400 FibNode p = null； // 要查找的节点
401
402 if（根==null）
403 回归根；
404
405 do {
406 if（t.key == 键）{
407 p = t；
408 断；
409 } 其他 {
410 if ((p = search(t.child, key)) != null)
411 断；
412  }
413 t = t.右；
414 } 同时（t！=根）；
415
416 返回 p;
417  }
418
419 /*
420  * 查找斐波那契堆中具有键值的节点
421 */
422 private FibNode 搜索(int key) {423 if（分钟==null）
424 返回 null；
425
426 返回 搜索(min, key);
427  }
428
429 /*
430  * 斐波那契堆中是否存在具有键值的节点。
431  * 存在则返回 true，否则返回 false。
432 */
433 public boolean 包含（int） 键）{
434返回搜索（键）！=null？ 真：假；
435  }
436
437 /*
438  * 删除节点
439 */
440 private void 删除（FibNode 节点）{
441 int m = 最小键；
442 减少（节点，m-1）；
443 removeMin();
444  }
445
446 公共 void 删除（int） 键）{
447 if（分钟==null）448 返回 ;
449
450 FibNode 节点 = search(key);
451 if（节点==null）
452 返回 ;
453
454  删除（节点）；
455  }
456
457 /*
458  * 摧毁斐波那契堆
459 */
460 private void destroyNode(FibNode 节点) {
461 if（节点==null）
462 返回；
463
464 FibNode 起始 = 节点；
465 do {
466  destroyNode(node.child);
467 // 销毁该节点并将该节点指向下一个
468节点=节点.right;
469节点.left = null;
470 } while（节点！=开始）；
471  }
472
473 public void destroy() {
474  destroyNode(min);475  }
476
477 /*
478  * 打印“斐波那契堆”
479  *
480  * 参数说明：
481  * 节点 -- 当前节点
482  * prev -- 当前节点的上一个节点（父节点或兄弟节点）
483  * 方向 -- 1，表示当前节点是左子节点；
484  * 2，表示当前节点是兄弟节点。
485 */
486 private void print(FibNode 节点, FibNode 上一个,   int方向）{
487 FibNode 起始=节点；
488
489 if（节点==null）
490 返回 ;
491 do {
492 if（方向==1）
493 System.out.printf("%8d(%d)是%2d的孩子\n",node.key,node. Degree,prev.key);
494 其他
495 System.out.printf("%8d(%d)是%2d的下一个\n",node.key,node. Degree,prev.key);
496497 if（节点.child！= null）
498 print(node.child, 节点, 1);
499
500 // 兄弟节点
501 上一个 = 节点；
502节点=节点.right;
503方向 = 2；
504 } 同时（节点！=开始）；
505  }
506
507 公共 void print() {
508 if（分钟==null）
509 返回 ;
510
511 int i=0；
512 FibNode p = 分钟；
513 System.out.printf("==斐波那契堆的详细信息: ==\n");
514 do {
515i++；
516 System.out.printf("%2d.%4d(%d)是根\n", i, p.key, p. Degree);
517
518 print(p.child, p, 1);
519 p = p.右；
520 } 同时（p！= 分钟）；521 System.out.printf("\n");
522  }
523 }

查看代码

斐波那契堆测试程序（m.gsm-guard.net）

 1 /**
 2  * Java 语言：斐波那契堆
 3  *
 4  * @author skywang
 5  * @日期 2014/04/07
 6 */
 7
 8 公共 类 主要{
 9
 10 私人 静态  最终 布尔值调试 = 假；
 11
 12 // 共 8 个 
 13 私人 静态  int a[] = {12, 7, 25, 15, 28, 33, 41, 1}；
 14 // 共14个 15 私人 静态  int b[] = {18, 35, 20, 42, 9,
 16 31, 23, 6, 48, 11,
 17 24, 52, 13, 2 };
 18
 19 // 验证“基本信息（斐波那契堆结构）”
 20 公共 静态  void testBasic() {
 21 FibHeap hb=new FibHeap();
 22
 23 // 斐波那契堆 hb
 24 System.out.printf("== 添加到斐波那契堆(hb):");
 25 对于(int i=0; i) {
 26 System.out.printf("%d", b[i]);
 27  hb.insert(b[i]);
 28  }
 29 System.out.printf("\n"); 30 System.out.printf("==斐波那契堆(hb)删除最小节点\n");
 31  hb.removeMin();
 32 hb.print(); //打印斐波那契堆hb
 33  }
 34
 35 // 验证“插入操作”
 36 公共 静态  void testInsert() {
 37 FibHeap ha=new FibHeap();
 38
 39 // 斐波那契数列 ha
 40 System.out.printf("== 添加到斐波那契堆(ha):");
 41 对于(int i=0; i) {
 42 System.out.printf("%d", a[i]);
 43  ha.insert(a[i]);
 44  }
 45 System.out.printf("\n");
 46 System.out.printf("==斐波那契堆(ha)删除最小节点\n"); 47  ha.removeMin();
 48 ha.print(); //打印斐波那契堆ha
 49
 50 System.out.printf("==插入50\n");
 51 ha.insert(50);
 52  ha.print();
 53  }
 54
 55 // 验证“合并操作”
 56 公共 静态  void testUnion() {
 57 FibHeap ha=new FibHeap();
 58 FibHeap hb=new FibHeap();
 59
 60 // 斐波那契桩 ha
 61 System.out.printf("== 添加到斐波那契堆(ha):");
 62 对于(int i=0; i) {
 63 System.out.printf("%d", a[i]);
 64  ha.insert(a[i]);
 65  } 66 System.out.printf("\n");
 67 System.out.printf("==斐波那契堆(ha)删除最小节点\n");
 68  ha.removeMin();
 69 ha.print(); //打印斐波那契堆 ha
 70
 71 // 斐波那契堆 hb
 72 System.out.printf("== 添加到斐波那契堆(hb):");
 73 对于(int i=0; i) {
 74 System.out.printf("%d", b[i]);
 75  hb.insert(b[i]);
 76  }
 77 System.out.printf("\n");
 78 System.out.printf("==斐波那契堆(hb)删除最小节点\n");
 79  hb.removeMin();
 80 hb.print(); // 打印斐波那契堆 hb
 81
 82 // 将“斐波那契堆 hb”合并为“斐波那契堆 ha”。  83 System.out.printf("==合并ha和hb\n");
 84  ha.union(hb);
 85  ha.print();
 86  }
 87
 88 // 验证“删除最小节点”
 89 公共 静态  void testRemoveMin() {
 90 FibHeap ha=new FibHeap();
 91 FibHeap hb=new FibHeap();
 92
 93 // 斐波那契桩 ha
 94 System.out.printf("== 添加到斐波那契堆(ha):");
 95 对于(int i=0; i) {
 96 System.out.printf("%d", a[i]);
 97  ha.insert(a[i]);
 98  }
 99 System.out.printf("\n");
100 System.out.printf("==斐波那契堆(ha)删除最小节点\n");undefined125 // 验证“减少节点”
126 公共 静态 void  testDecrease() {
127 FibHeap hb=new FibHeap();
128
129 // 斐波那契桩 hb
130 System.out.printf("== 添加到斐波那契堆(hb):");
131 for(int i=0; i) {
132 System.out.printf("%d", b[i]);
133  hb.insert(b[i]);
134  }
135 System.out.printf("\n");
136 System.out.printf("==斐波那契堆(hb)删除最小节点\n");
137  hb.removeMin();
138 hb.print(); //打印斐波那契堆hb
139
140 System.out.printf("== 将 20 减少到 2\n");
141 hb.update(20, 2);
142  hb.print();
143  }
144
145 // 验证“增加节点”
146 公共 静态 void  testIncrease() {147 FibHeap hb=new FibHeap();
148
149 // 斐波那契堆 hb
150 System.out.printf("== 添加到斐波那契堆(hb):");
151 对于(int i=0; i ）{
152 System.out.printf("%d", b[i]);
153  hb.insert(b[i]);
154}
155 System.out.printf("\n");
156 System.out.printf("==斐波那契堆(hb)删除最小节点\n");
157  hb.removeMin();
158 hb.print(); //打印斐波那契堆hb
159
160 System.out.printf("== 将 20 增加到 60\n");
161 hb.update(20, 60);
162  hb.print();
163  }
164
165 // 验证“删除节点”
166 公共 静态 void  测试删除() {
167 FibHeap hb=new FibHeap();
168
169 // 斐波那契堆 hb170 System.out.printf("== 添加到斐波那契堆(hb):");
171 对于(int i=0; i ）{
172 System.out.printf("%d", b[i]);
173  hb.insert(b[i]);
174  }
175 System.out.printf("\n");
176 System.out.printf("==斐波那契堆(hb)删除最小节点\n");
177  hb.removeMin();
178 hb.print(); //打印斐波那契堆hb
179
180 System.out.printf("==删除节点20\n");
181 hb.remove(20);
182  hb.print();
183  }
184
185 公共 静态 void  main(String[] args) {
186 // 验证“基本信息（斐波那契堆结构）”
187  testBasic();
188 // 验证“插入操作”
189 //testInsert();
190 // 验证“合并操作”
191 //testUnion();192 // 验证“删除最小节点”
193 //testRemoveMin();
194 // 验证“减少节点”
195 //testDecrease();
196 // 验证“增加节点”
197 //testIncrease();
198 // 验证“删除节点”
199 //testDelete();
200  }
201 }

查看代码

斐波那契堆的 Java 测试程序

斐波那契堆的测试程序包括“插入”、“合并”、“增加”、“减少”、“删除”、“基本信息”等功能测试代码。默认运行“基本信息（验证斐波那契堆结构）”测试代码。您可以根据自己的需求验证相应的功能！

以下是基本信息测试代码的运行结果：

== 添加到斐波那契堆 (hb): 18 35 20 42 9 31 23 6 48 11 24 52 13 2
== 斐波那契堆（hb）删除最小节点
== 斐波那契堆详细信息：==
 1. 6(3) 是根
       9(0) 是 6 的孩子
      18(1) 是 9 的下一个
      35(0) 是 18 岁的孩子
      20(2) 是 18 的下一个
      42(0) 是 20 岁的孩子
      23(1) 是 42 的下一个
      31(0) 是 23 的孩子
 2. 11(2) 是根48(0) 是 11 的孩子
      24(1) 是 48 的下一个
      52(0) 是 24 的孩子
 3. 13(0) 是根