I am implementing Fibonacci Heap to improve on my Dijkstra's shortest path algorithm. My insert method works fine, and the next one I needed to do is extract-min. I am following CLRS. Please note some attributes mentioned in the book aren't in my implementation yet, as they are not needed for the functions so far, but I will add them later.
private static class FibonacciHeap {
/**
* Implementation of the node used in
* fibonacci heap. The nodes are stored
* as a circular doubly-linked list, making
* delete and insert operations easy, as
* well as being able to iterate through
* without being forced to keep track of the
* head
*/
private class Node {
/**
* The vertex this node is storing
*/
Vertex val;
/**
* Key used to know the order of vertices
*/
int key;
/**
* The left and right sibling in the list
*/
Node left, right;
/**
* Pointer to one of the child's
*/
Node child;
/**
* The amount of children this node has
*/
int degree;
/**
* Constructs a node with a value and key
*
* @param val the value of this node
* @param key the key of this node
*/
public Node(Vertex val, int key) {
this.val = val;
this.key = key;
}
/**
* Inserts a new node into this node's list.
* Inserts it to the left of this node, while
* maintaining the fact that it's circular
*
* @param newNode The new node to be inserted
*/
public void insert(Node newNode) {
newNode.left = left;
left.right = newNode;
newNode.right = this;
left = newNode;
if(newNode.key < min.key) {
min = newNode;
}
size++;
}
/**
* Removes this node from it's list
*/
public void remove() {
right.left = left;
left.right = right;
}
/**
* Inserts a new child into this nodes
* child list
*
* @param child The new node to be added as a child
*/
public void link(Node child) {
child.remove();
if(this.child == null) {
this.child = child;
} else {
this.child.insert(child);
}
degree ++;
}
/**
* Used for debugging. Will be removed after
* all operations work fine
*
* @return A string representation of this node
*/
@Override
public String toString() {
Node dummy = right;
StringBuilder sb = new StringBuilder();
sb.append(key).append(" -> (");
sb.append(dummy.child);
sb.append(") ");
while(dummy != this) {
sb.append(dummy.key).append(" -> (");
sb.append(dummy.child);
sb.append(") ");
dummy = dummy.right;
}
return sb.toString();
}
}
/**
* Pointer to the node with the smallest key
*/
private Node min;
/**
* Stores the number of nodes in the heap
*/
private int size;
/**
* Creates an empty Fibonacci Heap
*/
public FibonacciHeap() { }
/**
* Gets and returns the key with the
* smallest value
*
* @return the key with the smallest value
*/
public int getMin() {
if(min == null) {
throw new NoSuchElementException("Empty Fibonacci Heap");
}
return min.key;
}
/**
* Inserts a vertex along with a key. The
* key is the one used to measure whether
* this vertex is lesser than another
*
* @param vertex vertex to be added
* @param key key of the vertex
*/
public void insert(Vertex vertex, int key) {
if(min == null) {
min = new Node(vertex, key);
min.left = min;
min.right = min;
size = 1;
} else {
min.insert(new Node(vertex, key));
}
}
/**
* Removes the node with the smallest key from
* the heap, and updates the minimum node if needed
*
* @return The node with the smallest key prior to this method call
*/
public Vertex extractMin() {
if(isEmpty()) {
throw new NoSuchElementException("Empty Fibonacci Heap");
}
Vertex toReturn;
if(min == null) {
toReturn = null;
} else {
toReturn = min.val;
if(min.right == min) {
min = null;
} else {
min.remove();
min = min.right;
consolidate();
}
}
return toReturn;
}
/**
* Consolidates the heap. Consolidation is the process
* making every node in the root list have it's own
* unique degree. That is, every node in the top most
* layer has a unique amount of children
*/
private void consolidate() {
Node[] degrees = new Node[size];
degrees[min.degree] = min;
Node tempMin, dummy = (tempMin = min).right;
while(dummy != tempMin) {
if(dummy.key < min.key) {
min = dummy;
}
while(degrees[dummy.degree] != null) {
Node other = degrees[dummy.degree];
if(other.key < dummy.key) {
Node temp = dummy;
dummy = other;
other = temp;
}
dummy.link(other);
degrees[dummy.degree - 1] = null;
}
degrees[dummy.degree] = dummy;
}
}
/**
* Returns true if and only if the
* heap is empty
*
* @return if the heap is empty
*/
public boolean isEmpty() {
return min == null;
}
/**
* A string representation of this
* heap. Format of string is:
* node1 -> (node1.child.toString()) node2 -> (node2.child.toString()) ... noden -> (noden.child.toString())
* The string representation of the
* heap is the string representation of
* the minimum node
*
* @return A string representation of this heap
*/
@Override
public String toString() {
return min.toString();
}
}
This is the stack trace that it gives:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
at GraphTheory.ShortestPathAlgorithms.DijkstraShortestPath$FibonacciHeap.consolidate(DijkstraShortestPath.java:362)
at GraphTheory.ShortestPathAlgorithms.DijkstraShortestPath$FibonacciHeap.extractMin(DijkstraShortestPath.java:338)
at GraphTheory.ShortestPathAlgorithms.DijkstraShortestPath.main(DijkstraShortestPath.java:104)
The main error is given in the conditional statement of the inner while loop in the consolidate function. I also commented the line in the code. What is going wrong? My main testing method insert 10 random numbers from 1 - 10, and then extracts the minimum until it's empty. The error occurs the first time extract-min is called.
public static void main(String[] args) {
FibonacciHeap f = new FibonacciHeap();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 10; i ++) {
f.insert(new Vertex(i), (int) (Math.random() * 10));
}
while(!f.isEmpty()) {
System.out.println(f.extractMin());
}
}
Can't pinpoint the exact bug. But, I can tell you from experience that you should not find the minimum while consolidating. You consolidate and then you find the new minimum. You might get into trouble when you have multiple nodes with the same key and the one pointed to by min doesn't end up in the root list.
Also, while testing, don't use a random function. Create an array of arbitrary numbers and insert elements from the array into the heap.
I also don't understand how your implementation handles there being only one heap ordered tree in the Fib heap. What happens when you do an extract-min then?
You can find my Python implementation here if you need it.