/*
* Copyright (C) 2015 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.utils;
import java.util.*;
/**
*
* @author Edward Raff
* @param
*/
public class FibHeap
{
/**
* We access a given Fibonacci heap H by a pointer H:min to the root of a tree containing the minimum key. When a Fibonacci heap H is empty, H:min is NIL.
*/
FibNode min;
/**
* We rely on one other attribute for a Fibonacci heap H: H:n, the number of
* nodes currently in H
*/
int n;
List> H;
public FibHeap()
{
/**
* To make an empty Fibonacci heap, the MAKE-FIB-HEAP procedure
* allocates and returns the Fibonacci heap object H, where H:n D 0 and
* H:min D NIL; there are no trees in H.
*/
this.min = null;
this.n = 0;
}
public int size()
{
return n;
}
public FibNode insert(T value, double weight)
{
//FIB-HEAP-INSERT
@SuppressWarnings("unchecked")
FibNode x = new FibNode(value, weight);
x.p = null;
x.child = null;
if(min == null)
{
//6| create a root list for H containing just x
// H = new ArrayList>();
// H.add(x);
//7| H.min D x
min = x;
}
else
{
//8| insert x into H ’s root list
min = merge(min, x);//9 & 10 handled implicitly by the behavior of merge method
}
//11| H.n = H.n+1
this.n++;
return x;
}
public static FibHeap union(FibHeap A, FibHeap B)
{
FibHeap H = new FibHeap();
H.min = merge(A.min, B.min);
H.n = A.n + B.n;
return H;
}
private void consolidate()
{
ArrayList> A = new ArrayList>();
ArrayList> rootListCopy = new ArrayList>();
FibNode startingNode = min;
FibNode runner = startingNode;
do
{
rootListCopy.add(runner);
//go to the next item in the list
runner = runner.right;
}
while(runner != startingNode);//Yes, intentionally comparing objects. Circular link list. So once we reach the starting object we are done
for(FibNode w : rootListCopy)
delink(w);//we will fix this later by re-merging at the end
//4| for each node w in the root list of H
for(FibNode w : rootListCopy)
{
FibNode x = w;//5
int d = x.degree;//6
//7| while A[d] != NIL
while(A.size() <= d)
A.add(null);
while(A.get(d) != null)
{
//8| y = A[d] // another node with the same degree as x
FibNode y = A.get(d);
if(x.key > y.key)
{
FibNode tmp = y;
y = x;
x = tmp;
}
//11| FIB-HEAP-LINK(H,y,x)
// if(startingNode == y )//if y was our starting node, we need to change the start to avoid a loop
// startingNode = y.right;//otherwise looping through root list will never reach the original starting node
// if(y == w)//move w left so that when we move right later we get to the correct position
// w = w.left;//otherwise w will start looping through the child list isntead of the root list
link(y, x);
//12| A[d]=NIL
A.set(d, null);
//13| d=d+1
d++;
while(A.size() <= d)
A.add(null);
}
//14| A[d] = x
A.set(d, x);
}
//15| H.min = NIL
min = null;
for(FibNode x : A)
min = merge(min, x);
}
private void link(FibNode y, FibNode x)
{
//1| remove y from the root list of H
delink(y);
//2| make y a child of x, incrementing x.degree
x.addChild(y);
x.degree++;//adding y as a child
x.degree += y.degree;//and all of y's children
//3| y.mark = FALSE
y.mark = false;
}
public double getMinKey()
{
return min.key;
}
public T getMinValue()
{
return min.value;
}
public FibNode peekMin()
{
return min;
}
public FibNode removeMin()
{
//FIB-HEAP-EXTRACT-MIN
//1| z = H.min
FibNode z = min;
if(z != null)
{
min = delink(z);
//3| for each child x of z
if (z.child != null)
{
final FibNode startingNode = z.child;
FibNode x = startingNode;
do
{
x.p = null;//set parrent to null, we will add to the root list later
//go to the next item in the list
x = x.right;
}
while (x != startingNode);//Yes, intentionally comparing objects. Circular link list. So once we reach the starting object we are done
//now all the children are added to the root list in one call
min = merge(min, z.child);
z.child = null;//z has no more children
z.degree = 0;
}
else if (n == 1)//z had no children and was the only item in the whole heap
{
//so just set min to null
min = null;
}
if(min != null)
consolidate();//this will set min correctly no matter what
n--;
}
return z;
}
public void decreaseKey(FibNode x, double k)
{
if(k > x.key)
throw new RuntimeException("new key is greater than current key");
x.key = k;
FibNode y = x.p;
if(y != null && x.key < y.key)
{
cut(x, y);
cascadingCut(y);
}
if(x.key < min.key)
min = x;
}
/**
*
* @param x the child
* @param y the parent
*/
private void cut(FibNode x, FibNode y)
{
//1| remove x from the child list of y, decrementing y.degree
if(y.child == x)//if we removed but x was the child pointer, we would get messed up
y.child = delink(x);
else
delink(x);
y.degree--;//removal of 'x' from y
y.degree-= x.degree;//removal of everyone x owned from y
//2| add x to the root list of H
min = merge(min, x);
//3| x.p = NIL
x.p = null;
//4| x.mark = FALSE
x.mark = false;
}
private void cascadingCut(FibNode y)
{
//1.
FibNode z = y.p;
if(z != null)//2.
{
if(y.mark == false)//3.
y.mark = true;//4.
else
{
cut(y, z);
cascadingCut(z);
}
}
}
public static class FibNode
{
T value;
double key;
/**
* We store the number of children in the child list of node x in x.degree
*/
int degree;
/**
* The boolean-valued attribute x:mark indicates whether node x has lost
* a child since the last time x was made the child of another node.
* Newly created nodes are unmarked, and a node x becomes unmarked
* whenever it is made the child of another node.
*/
boolean mark = false;
/**
* a pointer to its parent
*/
FibNode p;
/**
* a pointer to any one of its children
*/
FibNode child;
FibNode left, right;
public FibNode(T value, double key)
{
this.degree = 0;
this.value = value;
this.key = key;
this.left = this.right = this;//yes, this is intentional. We make a linked list of 1 item, ourselves.
}
public T getValue()
{
return value;
}
public double getPriority()
{
return key;
}
/**
* Adds the given node directly to the children list of this node. THe
* {@link #p} value for {@code x} will be set automatically. The
* {@link #degree} of this node will not be adjusted, and must be
* incremented correctly by the caller
*
* @param x the node to add as a child of this node. Should be a
* singular item
*/
public void addChild(FibNode x)
{
if(this.child == null)
this.child = x;
else
this.child = merge(this.child, x);
x.p = this;
}
@Override
public String toString()
{
return value + "," + key;
}
}
/**
* Disconnects the given node from the list it is currently in.
*
* @param
* @param a the node to disconnect from its current list
* @return a node in the list that 'a' was originally apart of. Returns
* {@code null} if a was its own list (ie: a list of size 1, or no "list").
*/
private static FibNode delink(FibNode a)
{
if(a.left == a)//a is on its own, nothing to return
return null;
//else, a is in a list
FibNode a_left_orig = a.left;//link to the rest of the list that we can return
a.left.right = a.right;
a.right.left = a_left_orig;
//a no longer is in its original list, return link
//fix a's links to point to itself not that it has been de-linked from everyone else
a.left = a.right = a;
return a_left_orig;
}
/**
* Merges the two lists given by the two nodes. Works if either node represents a list of size 1 / is on its own. The node with the smaller value will be returned.
* @param
* @param a
* @param b
* @return the node with the smallest key value
*/
private static FibNode merge(FibNode a, FibNode b)
{
if(a == b)//handles a and b == null (returns null) or a and b are the same object (return the obj, don't make weird cycles
return a;
if(a == null)
return b;
if(b == null)
return a;
//else, two different non-null nodes, make a the smaller priority one so we always return smallest priority
if(a.key > b.key)
{
FibNode tmp = a;
a = b;
b = tmp;
}
//linked list insert. Indertion used since links can point to themselves if list is empty
FibNode a_right_orig = a.right;
a.right = b.right;
a.right.left = a;
b.right = a_right_orig;
b.right.left = b;
return a;
}
}
Ads help maintain this website.