2 zyg0413 zyg0413 于 2015.07.17 23:28 提问

斐波那契堆JAVA实现的问题 55C

最近在做用斐波那契堆改进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)

8个回答

devmiao
devmiao   Ds   Rxr 2015.07.17 23:32
devmiao
devmiao   Ds   Rxr 2015.07.17 23:33
zyg0413
zyg0413 算法已经看懂了,是程序的实现除了问题
2 年多之前 回复
ojj88s
ojj88s   2015.07.18 00:23

heap要设置为字段

ojj88s
ojj88s 回复zyg0413: 至于为什么root==null,我分析主要问题发生在consolidate()函数实现中,可以在这里多检查检查
2 年多之前 回复
ojj88s
ojj88s 回复zyg0413: 这个我又重新看了一下,你要明白那个报错是怎么发生的,就在那句extractMin()函数中的if(root==null){ return null;这里,你把这句return null注释掉,然后替换成return new FibonacciNode(1,2);就不会报错了,这时候会发现后面输出的数都是2.0,也就是刚刚输入的那个数字,这就说明root==null这个条件被提前触发了
2 年多之前 回复
zyg0413
zyg0413 什么意思,可以说清楚点吗
2 年多之前 回复
tongyi55555
tongyi55555   2015.07.18 11:14

两个问题:
一个是增加节点的时候左右节点赋值错误,深入理解双向链表,赋值是有顺序的:修改如下;

// 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;
    }
tongyi55555
tongyi55555 第一个问题,你的node.right.left = node;应该写成root.right.left=node;才能满足你插入右边的要求。第二个问题在后面的回复中。
2 年多之前 回复
zyg0413
zyg0413 第二个问题,我觉得你的想法太过简单。extractMin() 关键的不是取出最小值,而是保证取出后堆的性质不变。就是要将root节点的孩子全部加到根链表上,同时合并具有相同读书的节点。算法导论上有对应的算法。
2 年多之前 回复
zyg0413
zyg0413 第一个问题,我觉得增加节点并没有错误,我的应该是增加到root的右边,你的是左边。
2 年多之前 回复
zyg0413
zyg0413 第一个问题,我觉得增加节点并没有错误,我的应该是增加到root的右边,你的是左边。
2 年多之前 回复
strutce
strutce   Ds   Rxr 2015.07.18 11:19

当打印4的时候已经最小了,赋值为null保存
if(min.right==min){
this.root=root.child;
}
这说明你排序的时候算法出错,可惜斐波那契堆我这个看不懂,只能给你指出错误,不能修正

tongyi55555
tongyi55555   2015.07.18 16:59

第二个问题你取得名字叫extractMin,我的理解是你要从里面取最小值。实际你是想removeMin。下面是removeMin方法,里面会调用consolidate进行重新合并,这个的代码修改起来还不如重新自己写或者参考一下http://www.cnblogs.com/skywang12345/p/3659122.html,建议你可以看看这个链接中内容。

cuiwei1026522829
cuiwei1026522829   Ds   Rxr 2015.07.18 23:31
CSDNXIAOD
CSDNXIAOD   2015.07.17 23:31

java兔子问题(斐波那契数列)
数字问题之斐波那契数列全解
括号配对问题JAVA实现
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片