zyg0413 于 2015.07.17 23:28 提问

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{
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;
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;

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;
}
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{
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);
}
// 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
}

//recurse cut the parent' parent, until reach the root list
FibonacciNode parent = node.parent;
if (parent!=null) {
if(node.mark==false)
node.mark=true;
else{
cut(node, 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
at MST.FibonacciHeapTest.main(FibonacciHeapTest.java:10)

8个回答

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

heap要设置为字段

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

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

if(min.right==min){
this.root=root.child;
}

tongyi55555   2015.07.18 16:59

cuiwei1026522829      2015.07.18 23:31
CSDNXIAOD   2015.07.17 23:31

java兔子问题（斐波那契数列）

----------------------biu~biu~biu~~~在下问答机器人小D，这是我依靠自己的聪明才智给出的答案，如果不正确，你来咬我啊！