问题描述
- 斐波那契堆JAVA实现的问题
-
最近在做用斐波那契堆改进Prim算法的作业。但是Java代码调试了两个周还是有问题，只能正确输出前3项。
还有几天就要提交作业了，在次跪求大神们帮忙瞧瞧代码。
代码如下：
public class FibonacciNode {
FibonacciNode child, left, right, parent;int vertex;
float element;
int degree;
Boolean mark;/** Constructor **/
public FibonacciNode(int vertex, float element) { this.right=this; this.left=this; this.parent=null; this.child=null; this.vertex=vertex; this.element=element; this.degree=0; this.mark=false; }}
public class FibonacciHeap {
FibonacciNode root;
int count;
public FibonacciHeap(){
root=null;
count=0;
}//Return the number of nodes of the current heap public int size(){ return count; } //Judge if the heap is empty public boolean isEmpty(){ return root==null; } //Clear the whole heap public void clear(){ root=null; count=0; } //Insert a node to the heap. public void insert(int vertex, Float element){ FibonacciNode node=new FibonacciNode(vertex, element); if(root==null) root=node; else{ addNode(node, root); if(root.element>node.element){ root=node; } } count++; } //Add b to the tail of a //Notify that a and b are both the heads of a double-linked list private void catList(FibonacciNode a, FibonacciNode b){ FibonacciNode tmp= a.right; a.right =b.right; b.right.left= a; b.right= tmp; tmp.left= b; } //Get the minimum node of the heap and remove it from the heap public FibonacciNode extractMin(){ if(root==null){ return null; } if(root.child!=null){ FibonacciNode m = root; FibonacciNode start=root.child; for(int i=0; i<m.degree; i++){ if(start!=null){ start.parent=null; addNode(start, root); start=start.right; } } } //remove root from the root list of heap FibonacciNode min=root; min.left.right=min.right; min.right.left=min.left; //if min.right==min, then the root of the heap has no child if(min.right==min){ this.root=null; } else{ root=min.right; consolidate(); } //decrease the number of the nodes count--; return min; } /* // 将min每一个儿子(儿子和儿子的兄弟)都添加到"斐波那契堆的根链表"中 while (m.child != null){ FibonacciNode child=m.child; removeNode(child); if(child.right==child) m.child=null; else m.child=child.right; addNode(child, min); child.parent=null; } *//*
if(min.child!=null){ //set all the min's child's parent as null
System.out.println("2:22222");
FibonacciNode startChild=min.child;
startChild.parent=null;
for(FibonacciNode x=startChild.right; x!=startChild; x=x.right){
x.parent=null;System.out.println("3:22222"); } //merge the children to the root list catList(root, startChild); } */ //unify two node if they have the same degree private void consolidate() { FibonacciNode[] cons=new FibonacciNode[this.count]; for(int i=0; i<this.count; i++) cons[i] = null; while (root!=null) { FibonacciNode x =root; if(x==x.right) root=null; else{ removeNode(x); root=x.right; } int d=x.degree; while(cons[d]!=null) { FibonacciNode y=cons[d]; if (x.element>y.element) { FibonacciNode tmp=x; x=y; y=tmp; } link(y, x); cons[d]=null; d++; } cons[d] = x; } root = null; for(int i=0; i<cons.length; i++){ if(cons[i] != null) { if(root == null) root = cons[i]; else{ addNode(cons[i], root); if ((cons[i]).element < root.element) root = cons[i]; } } } } //remove node1 from the root list and make it as node2's child private void link(FibonacciNode node1, FibonacciNode node2) { // remove node1 from the root list node1.left.right = node1.right; node1.right.left = node1.left; // set node as root's child if (node2.child == null) node2.child = node1; else{ node1.right=node2.child.right; node2.child.right=node1; node1.left=node2.child; node1.right.left=node1; } node1.parent = node2; node2.degree++; node1.mark = false; } //add node to the list rooted at root private void addNode(FibonacciNode node, FibonacciNode root) { node.left=root; node.right=root.right; root.right=node; node.right.left=node; } public void decreaseKey(FibonacciNode node, int key) { if (key > node.element) { System.out.println("decrease failed: the new key is no smaller than current key"); return; } if (root==null||node==null) return; node.element=key; FibonacciNode parent = node.parent; //if parent is null or node's element is no smaller than it's parent's, nothing is needed to be done if (parent!=null&&(node.element<parent.element)) { //remove node and add it to the root list cut(node, parent); cascadingCut(parent); } // update the root node if (node.element<root.element) root=node; } private void removeNode(FibonacciNode node) { node.left.right = node.right; node.right.left = node.left; } private void renewDegree(FibonacciNode parent){ parent.degree -= 1; if(parent. parent != null) renewDegree(parent.parent); } //remove node from it's parent and add it to the root list private void cut(FibonacciNode node, FibonacciNode parent) { removeNode(node); renewDegree(parent); //node has no sibling if (node==node.right) parent.child=null; else parent.child=node.right; node.parent=null; node.left=node.right=node; node.mark=false; //add to the root list of heap addNode(node, root); } //recurse cut the parent' parent, until reach the root list private void cascadingCut(FibonacciNode node) { FibonacciNode parent = node.parent; if (parent!=null) { if(node.mark==false) node.mark=true; else{ cut(node, parent); cascadingCut(parent); } } } //Add heap other to the current heap public void union(FibonacciHeap other) { if (this.root==null) //this is empty, just return the othe this.root=other.root; else if((other.root)!=null) {// both this and other are not empty catList(this.root, other.root); if(this.root.element>other.root.element) this.root=other.root; } this.count=this.count+other.count; other=null; return; }}
测试程序：
public class FibonacciHeapTest {
public static void main(String[] args){
FibonacciHeap heap=new FibonacciHeap();
for(int i=10; i>0; i--){
heap.insert(9-i, (float)i);
}for(int i=0; i<10; i++){
System.out.println(heap.extractMin().element);
}
}
}
运行结果：
1.0
2.0
3.0
4.0
Exception in thread "main" java.lang.NullPointerException
at MST.FibonacciHeapTest.main(FibonacciHeapTest.java:10)
解决方案
http://www.csdn123.com/html/mycsdn20140110/8e/8e18a40fb0eecc655cc068a1bb1d1ba4.html
解决方案二：
http://www.tuicool.com/articles/ryueAfu
解决方案三：
heap要设置为字段
解决方案四：
两个问题：
一个是增加节点的时候左右节点赋值错误，深入理解双向链表，赋值是有顺序的：修改如下；
// add node to the list rooted at root
private void addNode(FibonacciNode node, FibonacciNode root) {
// node.left = root;
// node.right = root.right;
// root.right = node;
// node.right.left = node;
// 修改
node.left = root.left;
root.left.right = node;
node.right = root;
root.left = node;
}
第二个问题，不明白你的extractMin的逻辑，没有那么复杂，最小的就是根节点，取出来，并赋值后面的即可，修改如下：
// Get the minimum node of the heap and remove it from the heap
public FibonacciNode extractMin() {
// 修改
FibonacciNode p = root;
if (p == p.right)
root = null;
else {
removeNode(p);
root = p.right;
}
p.left = p.right = p;
return p;
// if (root == null) {
// return null;
//
// }
//
// if (root.child != null) {
// FibonacciNode m = root;
// FibonacciNode start = root.child;
// for (int i = 0; i < m.degree; i++) {
// if (start != null) {
// start.parent = null;
// addNode(start, root);
// start = start.right;
// }
// }
// }
// // remove root from the root list of heap
// FibonacciNode min = root;
// min.left.right = min.right;
// min.right.left = min.left;
// // if min.right==min, then the root of the heap has no child
// if (min.right == min) {
// this.root = null;
// } else {
// root = min.right;
// consolidate();
// }
// // decrease the number of the nodes
// count--;
//
// return min;
}
解决方案五：
当打印4的时候已经最小了，赋值为null保存
if(min.right==min){
this.root=root.child;
}
这说明你排序的时候算法出错，可惜斐波那契堆我这个看不懂，只能给你指出错误，不能修正
解决方案六：
第二个问题你取得名字叫extractMin，我的理解是你要从里面取最小值。实际你是想removeMin。下面是removeMin方法，里面会调用consolidate进行重新合并，这个的代码修改起来还不如重新自己写或者参考一下http://www.cnblogs.com/skywang12345/p/3659122.html，建议你可以看看这个链接中内容。
解决方案七：
http://blog.csdn.net/bbirdsky/article/details/8964560
解决方案八：
java兔子问题（斐波那契数列）
数字问题之斐波那契数列全解
括号配对问题JAVA实现