最近在做用斐波那契堆改进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，建议你可以看看这个链接中内容。