/**
*
* id1:207032764
* name1:Nitsan Honen
* username1:nitsanhonen
* id2:206539496
* name2:Nitzan Zacharia
* username2:zacharia1
*
*/
/**
* FibonacciHeap
*
* An implementation of Fibonacci heap over positive integers.
*
*/
public class FibonacciHeap
{
public int numTrees;
public HeapNode first;
public HeapNode min;
public int totalLinks;
public int totalCuts;
public int size;
/**
*
* Constructor to initialize an empty heap.
*
*/
public FibonacciHeap()
{
numTrees = 0;
first = null;
min = null;
totalLinks = 0;
totalCuts = 0;
size = 0;
}
/**
*
* pre: key > 0
*
* Insert (key,info) into the heap and return the newly generated HeapNode.
*
* written by: Nitzan Z.
*
*/
public HeapNode insert(int key, String info) {
//acts as an envelope function for InsertHelper
HeapNode Node = new HeapNode(key, info);
return insertHelper(Node, true);
}
/**
*
* pre: isNew == true iff Node was created by the insert() method, false otherwise.
*
* Inserts the HeapNode Node into the heap and returns the newly inserted HeapNode.
*
* written by: Nitzan Z.
*
*/
private HeapNode insertHelper(HeapNode Node, boolean isNew){
int key = Node.key;
//if the heap is empty, insert Node as the first & minimal root
if(this.first==null) {
this.first=Node;
Node.next=Node;
Node.prev = Node;
this.min = Node;
}
//else, insert it as the first node of the root list,
//update the necessary prev/next pointers
else
{
Node.next = this.first;
Node.prev = this.first.prev;
this.first.prev.next = Node;
this.first.prev = Node;
this.first = Node;
if(key<this.min.key) { //update the min pointer if necessary
this.min = Node;
}
}
//if the node was generated by the Insert() method, update size
if(isNew) size ++;
numTrees++;
return Node;
}
/**
*
* Return the minimal HeapNode, null if empty.
*
* written by: Nitzan Z.
*
*/
public HeapNode findMin()
{
return this.min;
}
/**
*
* Recursive helper function that manages the actual process of consolidation
* for each tree in the heap
*
* pre: node.rank <= arr.length
*
* written by: Nitzan Z.
*
*/
private void recMove(HeapNode[] arr, HeapNode node) {
//base case: if there's no tree of the same rank in the array, place the node there.
//no need for another base case since the array size ensures will reach an empty cell.
if(arr[node.rank]==null)
{
arr[node.rank] = node;
this.numTrees--;
return;
}
//rec step: a tree of the same rank found
else {
int ind = node.rank;
HeapNode combined = linkTrees(node, arr[node.rank]); //link the trees
arr[ind] = null; //empty the cell
recMove(arr, combined); //continue recursively with the merged tree of rank: node.rank+1
}
}
/**
*
* Helper function that manages consolidation of the heap
*
* written by: Nitzan Z.
*
*/
private void consolidating() {
//builds an array of size> log(n)
HeapNode[] arr = new HeapNode[2+(int)(Math.log(size) / 0.48121)];
while(this.first!=null)
{
HeapNode node = this.first;
if(this.first.next == this.first) //if we reached the last root in the heap
{
this.first=null;
}
else
{
this.first=node.next; //remove the root from the heap
HeapNode last = node.prev;
last.next=this.first;
this.first.prev=last;
}
node.next = null;
node.prev=null;//detach the node from pointing to the heap
recMove(arr, node); //insert node to the array, link accordingly if needed
}
//update num of trees to zero before re-inserting the updated linked trees
this.numTrees=0;
this.min = null; //delete the pointer to the current min
int count = 0;
HeapNode minPointer = null;
//re-insert the trees to the heap, updating the number of trees and the minimum accordingly
for(int i=(arr.length-1);i>=0;i--)
{
if(arr[i]!=null) {
count++;
int key_root = arr[i].key;
HeapNode root_node = insertHelper(arr[i], false);
if (minPointer==null) {
minPointer = root_node;
}
else if(key_root<minPointer.key) {
minPointer = root_node;
}
}
}
this.min = minPointer;
this.numTrees = count;
}
/**
*
* Delete the minimal item
*
* written by: Nitzan Z.
*
*/
public void deleteMin() {
if(this.min==null) //if the heap is empty, nothing to delete
return;
deleteRoot(this.min); //remove the current min from the root list
// consolidate the heap (which will also update the min pointer) if the heap is not empty
if (this.size>0) consolidating();
}
/**
*
* given a pointer to a root, deletes it from the heap.
*
* written by: Nitzan Z.
*
*/
private void deleteRoot(HeapNode root)
{
//if the root is not a singleton, add its children to the root list, update relevant pointers
if(root.rank>0)
{
HeapNode child = root.child;
HeapNode node = child;
root.child = null;
child.prev.next = root.next;
root.next.prev = child.prev;
child.prev = root.prev;
root.prev.next = child;
while(node != null)
{
node.parent = null;
if(node.mark) {
node.mark = false;}
if(node.next == child)
{
break;
}
else node= node.next;
}
child.parent = null;
if(this.first==root) this.first=child;
this.numTrees += root.rank-1;
this.totalCuts += root.rank;
}
//if the heap will not be empty after deleting root, remove it and update relevant pointers
else if(this.numTrees>1)
{
root.next.prev = root.prev;
root.prev.next= root.next;
if(this.first==root) this.first=root.next;
this.numTrees--;
}
//if root is the only node in the heap, update the pointers so the heap is empty
else {
this.first=null;
this.numTrees = 0;
}
root.prev = null;
root.next = null;
if(size>0) {size --;} //update size if necessary
if(this.size==0) {this.min=null;} //update min if necessary
}
/**
*
* pre: 0<diff<x.key
*
* Decrease the key of x by diff and fix the heap.
*
* written by: Nitsan H.
*
*/
public void decreaseKey(HeapNode x, int diff)
{
x.key -= diff; //decrease key by diff
// if x's new key violates the heap property,
// fix it by cutting it from its parent (continue recursively if needed)
if(x.parent != null && x.key < x.parent.key){
cascadingCuts(x);
}
//if x is a root, update the min if necessary
else if(x.parent == null && x.key < this.min.key){this.min = x;}
}
/**
*
* Delete the x from the heap.
*
* written by: Nitsan H.
*
*/
public void delete(HeapNode x)
{
if(x == this.min){ //if x is the minimal element, perform deleteMin()
deleteMin();
return;
}
HeapNode min = this.min;
//if x is not a root, perform decreaseKey() to turn it to one prior to deletion.
if(x.parent != null){
int diff = x.key - x.parent.key + 1;
decreaseKey(x, diff);
}
//decreaseKey might change the minimum to be x,
//so we move the pointer back to the real minimum
this.min = min;
deleteRoot(x); //delete x, which is now a root
}
/**
*
* Return the total number of links.
*
* written by: Nitzan Z.
*
*/
public int totalLinks()
{
return this.totalLinks;
}
/**
*
* Return the total number of cuts.
*
* written by: Nitzan Z.
*
*/
public int totalCuts()
{
return this.totalCuts;
}
/**
*
* Meld the heap with heap2
*
* written by: Nitsan H.
*
*/
public void meld(FibonacciHeap heap2)
{
//update the necessary values to be the sum (of said values) of both heaps
this.size += heap2.size;
this.totalLinks += heap2.totalLinks;
this.totalCuts += heap2.totalCuts;
//if both heaps are not empty, concatenate them
if(this.numTrees != 0 && heap2.numTrees != 0){
HeapNode first2 = heap2.first;
HeapNode last1 = this.first.prev;
this.first.prev = first2.prev;
first2.prev.next = this.first;
first2.prev = last1;
last1.next = first2;
if(heap2.min.key < this.min.key){this.min = heap2.min;} //update min if necessary
}
//if current heap is empty, update its pointers to be the ones of heap2
else if(this.numTrees == 0 && heap2.numTrees != 0){
this.first = heap2.first;
this.min = heap2.min;
}
this.numTrees += heap2.numTrees;
}
/**
*
* Return the number of elements in the heap
*
* written by: Nitsan H.
*
*/
public int size()
{
return this.size;
}
/**
*
* Return the number of trees in the heap.
*
* written by: Nitsan H.
*
*/
public int numTrees()
{
return this.numTrees;
}
/**
*
* pre: root1.rank == root2.rank
*
* Link two trees of the same rank
*
* written by: Nitsan H.
*
*/
private HeapNode linkTrees(HeapNode root1, HeapNode root2){
HeapNode minRoot = root2;
HeapNode maxRoot = root1;
//update the pointers to determine which root will be the root of the merged tree
// and which will be its child
if(root1.key < root2.key){
minRoot = root1;
maxRoot = root2;
}
HeapNode tempChild = minRoot.child;
minRoot.child = maxRoot;
maxRoot.parent = minRoot;
//if minRoot has children, update the necessary pointers to add maxRoot to its children list
if(tempChild != null){
maxRoot.next = tempChild;
maxRoot.prev = tempChild.prev;
tempChild.prev = maxRoot;
maxRoot.prev.next = maxRoot;
}
else{ //else, insure minRoot's children list (containing only maxRoot) is circular.
maxRoot.prev = maxRoot;
maxRoot.next = maxRoot;
}
minRoot.rank++;
this.totalLinks++;
return minRoot;
}
/**
*
* pre: childNode.parent in not null
*
* Cut a node from its parent and insert as a new tree to the heap
*
* written by: Nitsan H.
*
*/
private void cut(HeapNode childNode){
totalCuts++;
HeapNode parent = childNode.parent;
childNode.parent = null;
childNode.mark = false;
parent.rank--;
if(childNode.next == childNode){ //if parent was of rank 1, delete the child pointer
parent.child = null;
}
else{ // if the parent had other children, update the necessary pointers
parent.child = childNode.next;
childNode.prev.next = childNode.next;
childNode.next.prev = childNode.prev;
}
//add childNode to the root list of the heap
//by creating a new heap and melding it with the original one.
FibonacciHeap newHeap = new FibonacciHeap();
newHeap.numTrees++;
newHeap.first = childNode;
newHeap.min = childNode;
childNode.next = childNode;
childNode.prev = childNode;
meld(newHeap);
}
/**
*
* Recursively cuts a node's parent from its grandparent if the parent is marked
*
* written by: Nitsan H.
*
*/
private void cascadingCuts(HeapNode childNode){
HeapNode parent = childNode.parent;
if(parent != null){ //performs a cut only if childNode is not a root
cut(childNode);
if(parent.parent != null){
//base case: if childNode has a parent which is not marked, mark it.
if(!parent.mark){
parent.mark = true;
}
else{ //rec step: if childNode has a marked parent, continue recursively
cascadingCuts(parent);
}
}
}
}
/**
* Class implementing a node in a Fibonacci Heap.
*
*/
public static class HeapNode{
public int key;
public String info;
public HeapNode child;
public HeapNode next;
public HeapNode prev;
public HeapNode parent;
public int rank;
public boolean mark;
public HeapNode(int key, String val)
{
this.key = key;
this.info = val;
child = null;
next = null;
prev = null;
parent = null;
rank = 0;
mark = false;
}
}
}