Fibonacci Heap
G
d
package com.thealgorithms.datastructures.heaps;
/**
* The {@code FibonacciHeap} class implements a Fibonacci Heap data structure,
* which is a collection of trees that satisfy the minimum heap property.
* This heap allows for efficient merging of heaps, as well as faster
* decrease-key and delete operations compared to other heap data structures.
*
* <p>Key features of the Fibonacci Heap include:
* <ul>
* <li>Amortized O(1) time complexity for insert and decrease-key operations.</li>
* <li>Amortized O(log n) time complexity for delete and delete-min operations.</li>
* <li>Meld operation that combines two heaps in O(1) time.</li>
* <li>Potential function that helps analyze the amortized time complexity.</li>
* </ul>
*
* <p>This implementation maintains additional statistics such as the total number
* of link and cut operations performed during the lifetime of the heap, which can
* be accessed through static methods.
*
* <p>The Fibonacci Heap is composed of nodes represented by the inner class
* {@code HeapNode}. Each node maintains a key, rank, marked status, and pointers
* to its children and siblings. Nodes can be linked and cut as part of the heap
* restructuring processes.
*
* @see HeapNode
*/
public class FibonacciHeap {
private static final double GOLDEN_RATIO = (1 + Math.sqrt(5)) / 2;
private HeapNode min;
private static int totalLinks = 0;
private static int totalCuts = 0;
private int numOfTrees = 0;
private int numOfHeapNodes = 0;
private int markedHeapNodesCounter = 0;
/*
* a constructor for an empty Heap
* set the min to be null
*/
public FibonacciHeap() {
this.min = null;
}
/*
* a constructor for a Heap with one element
* set the min to be the HeapNode with the given key
* @pre key>=0
* @post empty == false
*/
public FibonacciHeap(int key) {
this.min = new HeapNode(key);
this.numOfTrees++;
this.numOfHeapNodes++;
}
/*
* check if the heap is empty
* $ret == true - if the tree is empty
*/
public boolean empty() {
return (this.min == null);
}
/**
* Creates a node (of type HeapNode) which contains the given key, and inserts it into the heap.
*
* @pre key>=0
* @post (numOfnodes = = $prev numOfnodes + 1)
* @post empty == false
* $ret = the HeapNode we inserted
*/
public HeapNode insert(int key) {
HeapNode toInsert = new HeapNode(key); // creates the node
if (this.empty()) {
this.min = toInsert;
} else { // tree is not empty
min.setNext(toInsert);
this.updateMin(toInsert);
}
this.numOfHeapNodes++;
this.numOfTrees++;
return toInsert;
}
/**
* Delete the node containing the minimum key in the heap
* updates new min
*
* @post (numOfnodes = = $prev numOfnodes - 1)
*/
public void deleteMin() {
if (this.empty()) {
return;
}
if (this.numOfHeapNodes == 1) { // if there is only one tree
this.min = null;
this.numOfTrees--;
this.numOfHeapNodes--;
return;
}
// change all children's parent to null//
if (this.min.child != null) { // min has a child
HeapNode child = this.min.child;
HeapNode tmpChild = child;
child.parent = null;
while (child.next != tmpChild) {
child = child.next;
child.parent = null;
}
}
// delete the node//
if (this.numOfTrees > 1) {
(this.min.prev).next = this.min.next;
(this.min.next).prev = this.min.prev;
if (this.min.child != null) {
(this.min.prev).setNext(this.min.child);
}
} else { // this.numOfTrees = 1
this.min = this.min.child;
}
this.numOfHeapNodes--;
this.successiveLink(this.min.getNext());
}
/**
* Return the node of the heap whose key is minimal.
* $ret == null if (empty==true)
*/
public HeapNode findMin() {
return this.min;
}
/**
* Meld the heap with heap2
*
* @pre heap2 != null
* @post (numOfnodes = = $prev numOfnodes + heap2.numOfnodes)
*/
public void meld(FibonacciHeap heap2) {
if (heap2.empty()) {
return;
}
if (this.empty()) {
this.min = heap2.min;
} else {
this.min.setNext(heap2.min);
this.updateMin(heap2.min);
}
this.numOfTrees += heap2.numOfTrees;
this.numOfHeapNodes += heap2.numOfHeapNodes;
}
/**
* Return the number of elements in the heap
* $ret == 0 if heap is empty
*/
public int size() {
return this.numOfHeapNodes;
}
/**
* Return a counters array, where the value of the i-th index is the number of trees with rank i
* in the heap. returns an empty array for an empty heap
*/
public int[] countersRep() {
if (this.empty()) {
return new int[0]; /// return an empty array
}
int[] rankArray = new int[(int) Math.floor(Math.log(this.size()) / Math.log(GOLDEN_RATIO)) + 1]; // creates the array
rankArray[this.min.rank]++;
HeapNode curr = this.min.next;
while (curr != this.min) {
rankArray[curr.rank]++;
curr = curr.next;
}
return rankArray;
}
/**
* Deletes the node x from the heap (using decreaseKey(x) to -1)
*
* @pre heap contains x
* @post (numOfnodes = = $prev numOfnodes - 1)
*/
public void delete(HeapNode x) {
this.decreaseKey(x, x.getKey() + 1); // change key to be the minimal (-1)
this.deleteMin(); // delete it
}
/**
* The function decreases the key of the node x by delta.
*
* @pre x.key >= delta (we don't realize it when calling from delete())
* @pre heap contains x
*/
private void decreaseKey(HeapNode x, int delta) {
int newKey = x.getKey() - delta;
x.key = newKey;
if (x.isRoot()) { // no parent to x
this.updateMin(x);
return;
}
if (x.getKey() >= x.parent.getKey()) {
return;
} // we don't need to cut
HeapNode prevParent = x.parent;
this.cut(x);
this.cascadingCuts(prevParent);
}
/**
* returns the current potential of the heap, which is:
* Potential = #trees + 2*#markedNodes
*/
public int potential() {
return numOfTrees + (2 * markedHeapNodesCounter);
}
/**
* This static function returns the total number of link operations made during the run-time of
* the program. A link operation is the operation which gets as input two trees of the same
* rank, and generates a tree of rank bigger by one.
*/
public static int totalLinks() {
return totalLinks;
}
/**
* This static function returns the total number of cut operations made during the run-time of
* the program. A cut operation is the operation which disconnects a subtree from its parent
* (during decreaseKey/delete methods).
*/
public static int totalCuts() {
return totalCuts;
}
/*
* updates the min of the heap (if needed)
* @pre this.min == @param (posMin) if and only if (posMin.key < this.min.key)
*/
private void updateMin(HeapNode posMin) {
if (posMin.getKey() < this.min.getKey()) {
this.min = posMin;
}
}
/*
* Recursively "runs" all the way up from @param (curr) and mark the nodes.
* stop the recursion if we had arrived to a marked node or to a root.
* if we arrived to a marked node, we cut it and continue recursively.
* called after a node was cut.
* @post (numOfnodes == $prev numOfnodes)
*/
private void cascadingCuts(HeapNode curr) {
if (!curr.isMarked()) { // stop the recursion
curr.mark();
if (!curr.isRoot()) {
this.markedHeapNodesCounter++;
}
} else {
if (curr.isRoot()) {
return;
}
HeapNode prevParent = curr.parent;
this.cut(curr);
this.cascadingCuts(prevParent);
}
}
/*
* cut a node (and his "subtree") from his origin tree and connect it to the heap as a new tree.
* called after a node was cut.
* @post (numOfnodes == $prev numOfnodes)
*/
private void cut(HeapNode curr) {
curr.parent.rank--;
if (curr.marked) {
this.markedHeapNodesCounter--;
curr.marked = false;
}
if (curr.parent.child == curr) { // we should change the parent's child
if (curr.next == curr) { // curr do not have brothers
curr.parent.child = null;
} else { // curr have brothers
curr.parent.child = curr.next;
}
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
curr.next = curr;
curr.prev = curr;
curr.parent = null;
this.min.setNext(curr);
this.updateMin(curr);
this.numOfTrees++;
totalCuts++;
}
/*
*
*/
private void successiveLink(HeapNode curr) {
HeapNode[] buckets = this.toBuckets(curr);
this.min = this.fromBuckets(buckets);
}
/*
*
*/
private HeapNode[] toBuckets(HeapNode curr) {
HeapNode[] buckets = new HeapNode[(int) Math.floor(Math.log(this.size()) / Math.log(GOLDEN_RATIO)) + 1];
curr.prev.next = null;
HeapNode tmpCurr;
while (curr != null) {
tmpCurr = curr;
curr = curr.next;
tmpCurr.next = tmpCurr;
tmpCurr.prev = tmpCurr;
while (buckets[tmpCurr.rank] != null) {
tmpCurr = this.link(tmpCurr, buckets[tmpCurr.rank]);
buckets[tmpCurr.rank - 1] = null;
}
buckets[tmpCurr.rank] = tmpCurr;
}
return buckets;
}
/*
*
*/
private HeapNode fromBuckets(HeapNode[] buckets) {
HeapNode tmpMin = null;
this.numOfTrees = 0;
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
this.numOfTrees++;
if (tmpMin == null) {
tmpMin = buckets[i];
tmpMin.next = tmpMin;
tmpMin.prev = tmpMin;
} else {
tmpMin.setNext(buckets[i]);
if (buckets[i].getKey() < tmpMin.getKey()) {
tmpMin = buckets[i];
}
}
}
}
return tmpMin;
}
/*
* link between two nodes (and their trees)
* defines the smaller node to be the parent
*/
private HeapNode link(HeapNode c1, HeapNode c2) {
if (c1.getKey() > c2.getKey()) {
HeapNode c3 = c1;
c1 = c2;
c2 = c3;
}
if (c1.child == null) {
c1.child = c2;
} else {
c1.child.setNext(c2);
}
c2.parent = c1;
c1.rank++;
totalLinks++;
return c1;
}
/**
* public class HeapNode
* each HeapNode belongs to a heap (Inner class)
*/
public class HeapNode {
public int key;
private int rank;
private boolean marked;
private HeapNode child;
private HeapNode next;
private HeapNode prev;
private HeapNode parent;
/*
* a constructor for a heapNode withe key @param (key)
* prev == next == this
* parent == child == null
*/
public HeapNode(int key) {
this.key = key;
this.marked = false;
this.next = this;
this.prev = this;
}
/*
* returns the key of the node.
*/
public int getKey() {
return this.key;
}
/*
* checks whether the node is marked
* $ret = true if one child has been cut
*/
private boolean isMarked() {
return this.marked;
}
/*
* mark a node (after a child was cut)
* @inv root.mark() == false.
*/
private void mark() {
if (this.isRoot()) {
return;
} // check if the node is a root
this.marked = true;
}
/*
* add the node @param (newNext) to be between this and this.next
* works fine also if @param (newNext) does not "stands" alone
*/
private void setNext(HeapNode newNext) {
HeapNode tmpNext = this.next;
this.next = newNext;
this.next.prev.next = tmpNext;
tmpNext.prev = newNext.prev;
this.next.prev = this;
}
/*
* returns the next node to this node
*/
private HeapNode getNext() {
return this.next;
}
/*
* check if the node is a root
* root definition - this.parent == null (uppest in his tree)
*/
private boolean isRoot() {
return (this.parent == null);
}
}
}
