Fibonacci heap
Published , updated
A Fibonacci heap is a heap data structure similar to the binomial heap, only with a few modifications and a looser structure. The Fibonacci heap was designed in order to improve Dijkstra’s shortest path algorithm from O(m \log n) to O(m + n \log n) by optimising the operations used most by the algorithm. Its name derives from the fact that the Fibonacci sequence is used in the complexity analysis of its operations.
The primary difference between the Fibonacci heap and the binomial heap is that it defers all ‘clean up’ jobs to a point where they are more convenient, guarenteeing Θ(1) for several operations. Due to the deferred clean up, the worst case time complexity of the delete and extract minimum operations is O(n), however they are O(\log n) amortised.
This article assumes some knowledge of the binomial heap data structure.
Time complexity
| Operation | Description | Complexity |
|---|---|---|
| Decrease key | Decreases an existing key to some value | Θ(1)* |
| Delete | Deletes a node given a reference to it | O(\log n)* |
| Extract minimum | Removes and returns the minimum value given a reference to it | O(\log n)* |
| Find minimum | Returns the minimum value | Θ(1) |
| Insert | Inserts a new value | Θ(1) |
| Union | Combine the heap with another to form a valid Fibonacci heap | Θ(1) |
* Amortised
Structure
Like the binomial heap, a Fibonacci heap is a collection of heap-ordered trees. They do not need to be binomial trees however, this is where the relaxation of some of the binomial heap’s properties comes in.
Each tree has an order just like the binomial heap that is based on the number of children. Nodes within a Fibonacci heap can be removed from their tree without restructuring them, so the order does not necessarily indicate the maximum height of the tree or number of nodes it contains.
Links
The pointers between nodes in a Fibonacci heap are very similar to that of the binomial heap, only that each node in a Fibonacci heap contains a doubly linked list of all its children. This allows node removal and child list concatenation to both be performed in linear time.
Note that the child node whose parent links to it is always the node with the smallest value among its siblings.
‘Marked’ nodes
An important part of the Fibonacci Heap is how it marks nodes within the trees. The decrease key operation marks a node when its child is cut from a tree, this allows it to track some history about each node. Essentially the marking of nodes allows us to track whether:
- The node has had no children cut (unmarked)
- The node has had a single child cut (marked)
- The node is about to have a second child cut (removing a child of a marked node)
When a second child is cut from its parent, the parent is moved to the root list. This ensures that the structure of the Fibonacci heap does not stray too far from that of the binomial heap, which is one of the properties that enables the data structure to achieve its amortised time bounds.
Operations
Find minimum
A pointer to minimum node of the root list is always kept up to date.
Insert
Insert creates a new tree containing only the new node which is being added to the heap. The total number of nodes in the tree is incremented and the pointer to the minimum value is updated if necessary.
The insert operation of a fibonacci heap does not attempt to consolidate trees of equal order, opting instead to defer until a later time.
Union
Union concatenates the root lists of two Fibonacci heaps and sets the minimum node to which ever tree’s minimum node is smaller.
Decrease key
Decrease key lowers the key of a node. The node is then cut from the tree, joining the root list as its own tree. The parent of the node is then cut if it is marked, this continues for each anscestor until a parent that is not marked is encountered, which is then marked. The pointer to the minimum node is then updated if the node’s new value is less than the current minimum.
Extract minimum
Extract minimum is the most complex operation of a Fibonacci Heap as it’s where the actions that were deferred by the other operations occur. It starts by removing the minimum node from the root list and adding its children to the root list.
If the minimum was the only node in the root list, the pointer to the minimum node is set to the smallest node in the root list and the operation is completed.
If not, the ‘consolidate’ operation is performed which merges all trees of the same order together until there are no two trees of the same order. The minimum is then set to the smallest node in the root list.
Delete
Delete is performed by calling decrease key to reduce the node to negative infinity which pulls the node to the top of the tree. Extract minimum is then called on the node to remove it from the heap.
Code
/// <summary>
/// Represents a Fibonacci heap data structure capable of storing generic key-value pairs.
/// </summary>
public class FibonacciHeap<TKey, TValue> : IPriorityQueue<TKey, TValue>
where TKey : IComparable
{
private Node _minNode;
/// <summary>
/// The size of the heap.
/// </summary>
public int Size { get; private set; }
/// <summary>
/// Creates a Fibonacci heap.
/// </summary>
public FibonacciHeap()
{
_minNode = null;
Size = 0;
}
/// <summary>
/// Clears the heap's data, making it an empty heap.
/// </summary>
public void Clear()
{
_minNode = null;
Size = 0;
}
/// <summary>
/// Inserts a new key-value pair into the heap.
/// </summary>
/// <param name="key">The key to insert.</param>
/// <param name="val">The value to insert.</param>
/// <returns>The inserted node.</returns>
public INode<TKey, TValue> Insert(TKey key, TValue val)
{
Node node = new Node(key, val);
_minNode = MergeLists(_minNode, node);
Size++;
return node;
}
/// <summary>
/// Returns the minimum node from the heap.
/// </summary>
/// <returns>The heap's minimum node or undefined if the heap is empty.</returns>
public INode<TKey, TValue> FindMinimum()
{
return _minNode;
}
/// <summary>
/// Decreases a key of a node.
/// </summary>
/// </param name="node">The node to decrease the key of.</param>
/// </param name="newKey">The new key to assign to the node.</param>
public void DecreaseKey(INode<TKey, TValue> node, TKey newKey)
{
var casted = node as Node;
if (casted == null)
throw new ArgumentException("node must be a FibonacciHeap.Node");
DecreaseKey(casted, newKey);
}
/// <summary>
/// Decreases a key of a node.
/// </summary>
/// </param name="node">The node to decrease the key of.</param>
/// </param name="newKey">The new key to assign to the node.</param>
public void DecreaseKey(Node node, TKey newKey)
{
if (node == null)
throw new ArgumentException("node must be non-null.");
if (newKey.CompareTo(node.Key) > 0)
throw new ArgumentOutOfRangeException("New key is larger than old key.");
node.Key = newKey;
Node parent = node.Parent;
if (parent != null && node.CompareTo(parent) < 0)
{
Cut(node, parent);
CascadingCut(parent);
}
if (node.CompareTo(_minNode) < 0)
{
_minNode = node;
}
}
/// <summary>
/// Cut the link between a node and its parent, moving the node to the root list.
/// </summary>
/// <param name="node">The node being cut.</param>
/// <param name="parent">The parent of the node being cut.</param>
private void Cut(Node node, Node parent)
{
parent.Degree--;
parent.Child = (node.Next == node ? null : node.Next);
RemoveNodeFromList(node);
MergeLists(_minNode, node);
node.IsMarked = false;
}
/// <summary>
/// Perform a cascading cut on a node; mark the node if it is not marked, otherwise cut the
/// node and perform a cascading cut on its parent.
/// </summary>
/// <param name="node">The node being considered to be cut.</param>
private void CascadingCut(Node node)
{
Node parent = node.Parent;
if (parent != null)
{
if (node.IsMarked)
{
Cut(node, parent);
CascadingCut(parent);
}
else
{
node.IsMarked = true;
}
}
}
/// <summary>
/// Deletes a node.
/// </summary>
/// <param name="node">The node to delete.</param>
public void Delete(INode<TKey, TValue> node)
{
var casted = node as Node;
if (casted == null)
throw new ArgumentException("node must be a FibonacciHeap.Node");
Delete(casted);
}
/// <summary>
/// Deletes a node.
/// </summary>
/// <param name="node">The node to delete.</param>
public void Delete(Node node)
{
// This is a special implementation of decreaseKey that sets the
// argument to the minimum value. This is necessary to make generic keys
// work, since there is no MIN_VALUE constant for generic types.
Node parent = node.Parent;
if (parent != null)
{
Cut(node, parent);
CascadingCut(parent);
}
_minNode = node;
ExtractMinimum();
}
/// <summary>
/// Extracts and returns the minimum node from the heap.
/// </summary>
/// <returns>The heap's minimum node or undefined if the heap is empty.</returns>
public INode<TKey, TValue> ExtractMinimum()
{
Node extractedMin = _minNode;
if (extractedMin != null)
{
// Set parent to null for the minimum's children
if (extractedMin.Child != null)
{
Node child = extractedMin.Child;
do
{
child.Parent = null;
child = child.Next;
} while (child != extractedMin.Child);
}
Node nextInRootList = extractedMin.Next == extractedMin ? null : extractedMin.Next;
// Remove min from root list
RemoveNodeFromList(extractedMin);
Size--;
// Merge the children of the minimum node with the root list
_minNode = MergeLists(nextInRootList, extractedMin.Child);
if (nextInRootList != null)
{
_minNode = nextInRootList;
Consolidate();
}
}
return extractedMin;
}
/// <summary>
/// Merge all trees of the same order together until there are no two trees of the same
/// order.
/// </summary>
private void Consolidate()
{
if (_minNode == null)
return;
IList<Node> aux = new List<Node>();
var items = GetRootTrees();
foreach (var current in items)
{
//Node current = it.next();
var top = current;
while (aux.Count <= top.Degree + 1)
{
aux.Add(null);
}
// If there exists another node with the same degree, merge them
while (aux[top.Degree] != null)
{
if (top.Key.CompareTo(aux[top.Degree].Key) > 0)
{
Node temp = top;
top = aux[top.Degree];
aux[top.Degree] = temp;
}
LinkHeaps(aux[top.Degree], top);
aux[top.Degree] = null;
top.Degree++;
}
while (aux.Count <= top.Degree + 1)
{
aux.Add(null);
}
aux[top.Degree] = top;
}
_minNode = null;
for (int i = 0; i < aux.Count; i++)
{
if (aux[i] != null)
{
// Remove siblings before merging
aux[i].Next = aux[i];
aux[i].Prev = aux[i];
_minNode = MergeLists(_minNode, aux[i]);
}
}
}
/// <summary>
/// Gets all root-level trees of the heap.
/// </summary>
private IEnumerable<Node> GetRootTrees()
{
var items = new Queue<Node>();
Node current = _minNode;
do
{
items.Enqueue(current);
current = current.Next;
} while (_minNode != current);
return items;
}
/// <summary>
/// Removes a node from a node list.
/// </summary>
/// <param name="node">The node to remove.</param>
private void RemoveNodeFromList(Node node)
{
Node prev = node.Prev;
Node next = node.Next;
prev.Next = next;
next.Prev = prev;
node.Next = node;
node.Prev = node;
}
/// <summary>
/// Links two heaps of the same order together.
/// </summary>
/// <param name="max">The heap with the larger root.</param>
/// <param name="min">The heap with the smaller root.</param>
private void LinkHeaps(Node max, Node min)
{
RemoveNodeFromList(max);
min.Child = MergeLists(max, min.Child);
max.Parent = min;
max.IsMarked = false;
}
/// <summary>
/// Joins another heap to this heap.
/// </summary>
/// <param name="other">The other heap.</param>
public void Union(IPriorityQueue<TKey, TValue> other)
{
var casted = other as FibonacciHeap<TKey, TValue>;
if (casted == null)
throw new ArgumentException("other must be a FibonacciHeap");
Union(casted);
}
/// <summary>
/// Joins another heap to this heap.
/// </summary>
/// <param name="other">The other heap.</param>
public void Union(FibonacciHeap<TKey, TValue> other)
{
_minNode = MergeLists(_minNode, other._minNode);
Size += other.Size;
}
/// <summary>
/// Merge two lists of nodes together.
/// </summary>
/// <param name="a">The first list to merge.</param>
/// <param name="b">The second list to merge.</param>
/// <returns>The new minimum node from the two lists.</returns>
private Node MergeLists(Node a, Node b)
{
if (a == null && b == null)
return null;
if (a == null)
return b;
if (b == null)
return a;
Node temp = a.Next;
a.Next = b.Next;
a.Next.Prev = a;
b.Next = temp;
b.Next.Prev = b;
return a.CompareTo(b) < 0 ? a : b;
}
/// <summary>
/// Gets whether the heap is empty.
/// </summary>
public bool IsEmpty {
get { return _minNode == null; }
}
/// <summary>
/// A node object used to store data in the Fibonacci heap.
/// </summary>
public class Node : INode<TKey, TValue>
{
public TKey Key { get; set; }
public TValue Value { get; set; }
public int Degree { get; set; }
public Node Parent { get; set; }
public Node Child { get; set; }
public Node Prev { get; set; }
public Node Next { get; set; }
public bool IsMarked { get; set; }
/// <summary>
/// Creates a Fibonacci heap node.
/// </summary>
public Node()
{
}
/// <summary>
/// Creates a Fibonacci heap node initialised with a key and value.
/// </summary>
/// <param name="key">The key to use.</param>
/// <param name="val">The value to use.</param>
public Node(TKey key, TValue val)
{
Key = key;
Value = val;
Next = this;
Prev = this;
}
public int CompareTo(object other)
{
var casted = other as Node;
if (casted == null)
throw new NotImplementedException("Cannot compare to a non-Node object");
return this.Key.CompareTo(casted.Key);
}
}
}public class FibonacciHeap<T extends Comparable<T>> {
private Node<T> minNode;
private int size;
public FibonacciHeap() {
minNode = null;
size = 0;
}
private FibonacciHeap(Node<T> node) {
minNode = node;
size = 1;
}
private FibonacciHeap(Node<T> minNode, int size) {
this.minNode = minNode;
this.size = size;
}
public boolean isEmpty() {
return minNode == null;
}
public void clear() {
minNode = null;
size = 0;
}
public Node<T> insert(T key) {
Node<T> node = new Node<T>(key);
minNode = mergeLists(minNode, node);
size++;
return node;
}
public Node<T> findMinimum() {
return minNode;
}
public void decreaseKey(Node<T> node, T newKey) {
if (newKey.compareTo(node.key) > 0) {
throw new IllegalArgumentException("New key is larger than old key.");
}
node.key = newKey;
Node<T> parent = node.parent;
if (parent != null && node.compareTo(parent) < 0) {
cut(node, parent);
cascadingCut(parent);
}
if (node.compareTo(minNode) < 0) {
minNode = node;
}
}
private void cut(Node<T> node, Node<T> parent) {
removeNodeFromList(node);
parent.degree--;
mergeLists(minNode, node);
node.isMarked = false;
}
private void cascadingCut(Node<T> node) {
Node<T> parent = node.parent;
if (parent != null) {
if (node.isMarked) {
cut(node, parent);
cascadingCut(parent);
} else {
node.isMarked = true;
}
}
}
public void delete(Node<T> node) {
// This is a special implementation of decreaseKey that sets the
// argument to the minimum value. This is necessary to make generic keys
// work, since there is no MIN_VALUE constant for generic types.
node.isMinimum = true;
Node<T> parent = node.parent;
if (parent != null) {
cut(node, parent);
cascadingCut(parent);
}
minNode = node;
extractMin();
}
public Node<T> extractMin() {
Node<T> extractedMin = minNode;
if (extractedMin != null) {
// Set parent to null for the minimum's children
if (extractedMin.child != null) {
Node<T> child = extractedMin.child;
do {
child.parent = null;
child = child.next;
} while (child != extractedMin.child);
}
Node<T> nextInRootList = minNode.next == minNode ? null : minNode.next;
// Remove min from root list
removeNodeFromList(extractedMin);
size--;
// Merge the children of the minimum node with the root list
minNode = mergeLists(nextInRootList, extractedMin.child);
if (nextInRootList != null) {
minNode = nextInRootList;
consolidate();
}
}
return extractedMin;
}
private void consolidate() {
List<Node<T>> aux = new ArrayList<Node<T>>();
NodeListIterator<T> it = new NodeListIterator<T>(minNode);
while (it.hasNext()) {
Node<T> current = it.next();
while (aux.size() <= current.degree + 1) {
aux.add(null);
}
// If there exists another node with the same degree, merge them
while (aux.get(current.degree) != null) {
if (current.key.compareTo(aux.get(current.degree).key) > 0) {
Node<T> temp = current;
current = aux.get(current.degree);
aux.set(current.degree, temp);
}
linkHeaps(aux.get(current.degree), current);
aux.set(current.degree, null);
current.degree++;
}
while (aux.size() <= current.degree + 1) {
aux.add(null);
}
aux.set(current.degree, current);
}
minNode = null;
for (int i = 0; i < aux.size(); i++) {
if (aux.get(i) != null) {
// Remove siblings before merging
aux.get(i).next = aux.get(i);
aux.get(i).prev = aux.get(i);
minNode = mergeLists(minNode, aux.get(i));
}
}
}
private void removeNodeFromList(Node<T> node) {
Node<T> prev = node.prev;
Node<T> next = node.next;
prev.next = next;
next.prev = prev;
node.next = node;
node.prev = node;
}
private void linkHeaps(Node<T> max, Node<T> min) {
removeNodeFromList(max);
min.child = mergeLists(max, min.child);
max.parent = min;
max.isMarked = false;
}
// Union another fibonacci heap with this one
public void union(FibonacciHeap<T> other) {
minNode = mergeLists(minNode, other.minNode);
size += other.size;
}
// Merges two lists and returns the minimum node
public static <T extends Comparable<T>> Node<T> mergeLists(
Node<T> a, Node<T> b) {
if (a == null && b == null) {
return null;
}
if (a == null) {
return b;
}
if (b == null) {
return a;
}
Node<T> temp = a.next;
a.next = b.next;
a.next.prev = a;
b.next = temp;
b.next.prev = b;
return a.compareTo(b) < 0 ? a : b;
}
public void print() {
System.out.println("Fibonacci heap:");
if (minNode != null) {
minNode.print(0);
}
}
public static class Node<T extends Comparable<T>>
implements Comparable<Node<T>> {
private T key;
private int degree;
private Node<T> parent;
private Node<T> child;
private Node<T> prev;
private Node<T> next;
private boolean isMarked;
private boolean isMinimum;
public Node() {
key = null;
}
public Node(T key) {
this.key = key;
next = this;
prev = this;
}
public T getKey() {
return key;
}
public int compareTo(Node<T> other) {
return this.key.compareTo(other.key);
}
private void print(int level) {
Node<T> curr = this;
do {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < level; i++) {
sb.append(" ");
}
sb.append(curr.key.toString());
System.out.println(sb.toString());
if (curr.child != null) {
curr.child.print(level + 1);
}
curr = curr.next;
} while (curr != this);
}
}
// This Iterator is used to simplify the consolidate() method. It works by
// gathering a list of the nodes in the list in the constructor since the
// nodes can change during consolidation.
public static class NodeListIterator<T extends Comparable<T>>
implements Iterator<Node<T>> {
private Queue<Node<T>> items = new LinkedList<Node<T>>();
public NodeListIterator(Node<T> start) {
if (start == null) {
return;
}
Node<T> current = start;
do {
items.add(current);
current = current.next;
} while (start != current);
}
public boolean hasNext() {
return items.peek() != null;
}
public Node<T> next() {
return items.poll();
}
public void remove() {
throw new UnsupportedOperationException(
"NodeListIterator.remove is not implemented");
}
}
}'use strict';
/**
* Creates a Fibonacci heap.
*
* @constructor
* @param {function} customCompare An optional custom node comparison
* function.
*/
var FibonacciHeap = function (customCompare) {
this.minNode = undefined;
this.nodeCount = 0;
if (customCompare) {
this.compare = customCompare;
}
};
/**
* Clears the heap's data, making it an empty heap.
*/
FibonacciHeap.prototype.clear = function () {
this.minNode = undefined;
this.nodeCount = 0;
};
/**
* Decreases a key of a node.
*
* @param {Node} node The node to decrease the key of.
* @param {Object} newKey The new key to assign to the node.
*/
FibonacciHeap.prototype.decreaseKey = function (node, newKey) {
if (typeof node === 'undefined') {
throw new Error('Cannot decrease key of non-existent node');
}
if (this.compare({key: newKey}, {key: node.key}) > 0) {
throw new Error('New key is larger than old key');
}
node.key = newKey;
var parent = node.parent;
if (parent && this.compare(node, parent) < 0) {
cut(node, parent, this.minNode, this.compare);
cascadingCut(parent, this.minNode, this.compare);
}
if (this.compare(node, this.minNode) < 0) {
this.minNode = node;
}
};
/**
* Deletes a node.
*
* @param {Node} node The node to delete.
*/
FibonacciHeap.prototype.delete = function (node) {
// This is a special implementation of decreaseKey that sets the argument to
// the minimum value. This is necessary to make generic keys work, since there
// is no MIN_VALUE constant for generic types.
var parent = node.parent;
if (parent) {
cut(node, parent, this.minNode, this.compare);
cascadingCut(parent, this.minNode, this.compare);
}
this.minNode = node;
this.extractMinimum();
};
/**
* Extracts and returns the minimum node from the heap.
*
* @return {Node} node The heap's minimum node or undefined if the heap is
* empty.
*/
FibonacciHeap.prototype.extractMinimum = function () {
var extractedMin = this.minNode;
if (extractedMin) {
// Set parent to undefined for the minimum's children
if (extractedMin.child) {
var child = extractedMin.child;
do {
child.parent = undefined;
child = child.next;
} while (child !== extractedMin.child);
}
var nextInRootList;
if (extractedMin.next !== extractedMin) {
nextInRootList = extractedMin.next;
}
// Remove min from root list
removeNodeFromList(extractedMin);
this.nodeCount--;
// Merge the children of the minimum node with the root list
this.minNode = mergeLists(nextInRootList, extractedMin.child, this.compare);
if (this.minNode) {
this.minNode = consolidate(this.minNode, this.compare);
}
}
return extractedMin;
};
/**
* Returns the minimum node from the heap.
*
* @return {Node} node The heap's minimum node or undefined if the heap is
* empty.
*/
FibonacciHeap.prototype.findMinimum = function () {
return this.minNode;
};
/**
* Inserts a new key-value pair into the heap.
*
* @param {Object} key The key to insert.
* @param {Object} value The value to insert.
* @return {Node} node The inserted node.
*/
FibonacciHeap.prototype.insert = function (key, value) {
var node = new Node(key, value);
this.minNode = mergeLists(this.minNode, node, this.compare);
this.nodeCount++;
return node;
};
/**
* @return {boolean} Whether the heap is empty.
*/
FibonacciHeap.prototype.isEmpty = function () {
return this.minNode === undefined;
};
/**
* @return {number} The size of the heap.
*/
FibonacciHeap.prototype.size = function () {
if (this.isEmpty()) {
return 0;
}
return getNodeListSize(this.minNode);
};
/**
* Joins another heap to this heap.
*
* @param {FibonacciHeap} other The other heap.
*/
FibonacciHeap.prototype.union = function (other) {
this.minNode = mergeLists(this.minNode, other.minNode, this.compare);
this.nodeCount += other.nodeCount;
};
/**
* Compares two nodes with each other.
*
* @private
* @param {Object} a The first key to compare.
* @param {Object} b The second key to compare.
* @return {number} -1, 0 or 1 if a < b, a == b or a > b respectively.
*/
FibonacciHeap.prototype.compare = function (a, b) {
if (a.key > b.key) {
return 1;
}
if (a.key < b.key) {
return -1;
}
return 0;
};
/**
* Creates an Iterator used to simplify the consolidate() method. It works by
* making a shallow copy of the nodes in the root list and iterating over the
* shallow copy instead of the source as the source will be modified.
*
* @private
* @param {Node} start A node from the root list.
*/
var NodeListIterator = function (start) {
this.index = -1;
this.items = [];
var current = start;
do {
this.items.push(current);
current = current.next;
} while (start !== current);
};
/**
* @return {boolean} Whether there is a next node in the iterator.
*/
NodeListIterator.prototype.hasNext = function () {
return this.index < this.items.length - 1;
};
/**
* @return {Node} The next node.
*/
NodeListIterator.prototype.next = function () {
return this.items[++this.index];
};
/**
* Cut the link between a node and its parent, moving the node to the root list.
*
* @private
* @param {Node} node The node being cut.
* @param {Node} parent The parent of the node being cut.
* @param {Node} minNode The minimum node in the root list.
* @param {function} compare The node comparison function to use.
* @return {Node} The heap's new minimum node.
*/
function cut(node, parent, minNode, compare) {
node.parent = undefined;
parent.degree--;
if (node.next === node) {
parent.child = undefined;
} else {
parent.child = node.next;
}
removeNodeFromList(node);
minNode = mergeLists(minNode, node, compare);
node.isMarked = false;
return minNode;
}
/**
* Perform a cascading cut on a node; mark the node if it is not marked,
* otherwise cut the node and perform a cascading cut on its parent.
*
* @private
* @param {Node} node The node being considered to be cut.
* @param {Node} minNode The minimum node in the root list.
* @param {function} compare The node comparison function to use.
* @return {Node} The heap's new minimum node.
*/
function cascadingCut(node, minNode, compare) {
var parent = node.parent;
if (parent) {
if (node.isMarked) {
minNode = cut(node, parent, minNode, compare);
minNode = cascadingCut(parent, minNode, compare);
} else {
node.isMarked = true;
}
}
return minNode;
}
/**
* Merge all trees of the same order together until there are no two trees of
* the same order.
*
* @private
* @param {Node} minNode The current minimum node.
* @param {function} compare The node comparison function to use.
* @return {Node} The new minimum node.
*/
function consolidate(minNode, compare) {
var aux = [];
var it = new NodeListIterator(minNode);
while (it.hasNext()) {
var current = it.next();
// If there exists another node with the same degree, merge them
while (aux[current.degree]) {
if (compare(current, aux[current.degree]) > 0) {
var temp = current;
current = aux[current.degree];
aux[current.degree] = temp;
}
linkHeaps(aux[current.degree], current, compare);
aux[current.degree] = undefined;
current.degree++;
}
aux[current.degree] = current;
}
minNode = undefined;
for (var i = 0; i < aux.length; i++) {
if (aux[i]) {
// Remove siblings before merging
aux[i].next = aux[i];
aux[i].prev = aux[i];
minNode = mergeLists(minNode, aux[i], compare);
}
}
return minNode;
}
/**
* Removes a node from a node list.
*
* @private
* @param {Node} node The node to remove.
*/
function removeNodeFromList(node) {
var prev = node.prev;
var next = node.next;
prev.next = next;
next.prev = prev;
node.next = node;
node.prev = node;
}
/**
* Links two heaps of the same order together.
*
* @private
* @param {Node} max The heap with the larger root.
* @param {Node} min The heap with the smaller root.
* @param {function} compare The node comparison function to use.
*/
function linkHeaps(max, min, compare) {
removeNodeFromList(max);
min.child = mergeLists(max, min.child, compare);
max.parent = min;
max.isMarked = false;
}
/**
* Merge two lists of nodes together.
*
* @private
* @param {Node} a The first list to merge.
* @param {Node} b The second list to merge.
* @param {function} compare The node comparison function to use.
* @return {Node} The new minimum node from the two lists.
*/
function mergeLists(a, b, compare) {
if (!a && !b) {
return undefined;
}
if (!a) {
return b;
}
if (!b) {
return a;
}
var temp = a.next;
a.next = b.next;
a.next.prev = a;
b.next = temp;
b.next.prev = b;
return compare(a, b) < 0 ? a : b;
}
/**
* Gets the size of a node list.
*
* @private
* @param {Node} node A node within the node list.
* @return {number} The size of the node list.
*/
function getNodeListSize(node) {
var count = 0;
var current = node;
do {
count++;
if (current.child) {
count += getNodeListSize(current.child);
}
current = current.next;
} while (current !== node);
return count;
}
/**
* Creates a FibonacciHeap node.
*
* @constructor
* @private
*/
function Node(key, value) {
this.key = key;
this.value = value;
this.prev = this;
this.next = this;
this.degree = 0;
this.parent = undefined;
this.child = undefined;
this.isMarked = undefined;
}
module.exports = FibonacciHeap;// file: fibonacciHeap.ts
import { Node } from './node';
import { NodeListIterator } from './nodeListIterator';
import { FibonacciHeap as FibonacciHeapApi, CompareFunction, INode } from '@tyriar/fibonacci-heap';
export class FibonacciHeap<K, V> implements FibonacciHeapApi<K, V> {
private _minNode: Node<K, V> | null = null;
private _nodeCount: number = 0;
private _compare: CompareFunction<K, V>;
constructor(
compare?: CompareFunction<K, V>
) {
this._compare = compare ? compare : this._defaultCompare;
}
/**
* Clears the heap's data, making it an empty heap.
*/
public clear(): void {
this._minNode = null;
this._nodeCount = 0;
}
/**
* Decreases a key of a node.
* @param node The node to decrease the key of.
* @param newKey The new key to assign to the node.
*/
public decreaseKey(node: Node<K, V>, newKey: K): void {
if (!node) {
throw new Error('Cannot decrease key of non-existent node');
}
if (this._compare({key: newKey}, {key: node.key}) > 0) {
throw new Error('New key is larger than old key');
}
node.key = newKey;
const parent = node.parent;
if (parent && this._compare(node, parent) < 0) {
this._cut(node, parent, <Node<K, V>>this._minNode);
this._cascadingCut(parent, <Node<K, V>>this._minNode);
}
if (this._compare(node, <Node<K, V>>this._minNode) < 0) {
this._minNode = node;
}
}
/**
* Deletes a node.
* @param node The node to delete.
*/
public delete(node: Node<K, V>): void {
// This is a special implementation of decreaseKey that sets the argument to
// the minimum value. This is necessary to make generic keys work, since there
// is no MIN_VALUE constant for generic types.
const parent = node.parent;
if (parent) {
this._cut(node, parent, <Node<K, V>>this._minNode);
this._cascadingCut(parent, <Node<K, V>>this._minNode);
}
this._minNode = node;
this.extractMinimum();
}
/**
* Extracts and returns the minimum node from the heap.
* @return The heap's minimum node or null if the heap is empty.
*/
public extractMinimum(): Node<K, V> | null {
const extractedMin = this._minNode;
if (extractedMin) {
// Set parent to null for the minimum's children
if (extractedMin.child) {
let child = extractedMin.child;
do {
child.parent = null;
child = child.next;
} while (child !== extractedMin.child);
}
let nextInRootList = null;
if (extractedMin.next !== extractedMin) {
nextInRootList = extractedMin.next;
}
// Remove min from root list
this._removeNodeFromList(extractedMin);
this._nodeCount--;
// Merge the children of the minimum node with the root list
this._minNode = this._mergeLists(nextInRootList, extractedMin.child);
if (this._minNode) {
this._minNode = this._consolidate(this._minNode);
}
}
return extractedMin;
}
/**
* Returns the minimum node from the heap.
* @return The heap's minimum node or null if the heap is empty.
*/
public findMinimum(): Node<K, V> | null {
return this._minNode;
}
/**
* Inserts a new key-value pair into the heap.
* @param key The key to insert.
* @param value The value to insert.
* @return node The inserted node.
*/
public insert(key: K, value?: V): Node<K, V> {
const node = new Node(key, value);
this._minNode = this._mergeLists(this._minNode, node);
this._nodeCount++;
return node;
}
/**
* @return Whether the heap is empty.
*/
public isEmpty(): boolean {
return this._minNode === null;
}
/**
* @return The size of the heap.
*/
public size(): number {
if (this._minNode === null) {
return 0;
}
return this._getNodeListSize(this._minNode);
}
/**
* Joins another heap to this heap.
* @param other The other heap.
*/
public union(other: FibonacciHeap<K, V>): void {
this._minNode = this._mergeLists(this._minNode, other._minNode);
this._nodeCount += other._nodeCount;
}
/**
* Compares two nodes with each other.
* @param a The first key to compare.
* @param b The second key to compare.
* @return -1, 0 or 1 if a < b, a == b or a > b respectively.
*/
private _defaultCompare(a: INode<K, V>, b: INode<K, V>): number {
if (a.key > b.key) {
return 1;
}
if (a.key < b.key) {
return -1;
}
return 0;
}
/**
* Cut the link between a node and its parent, moving the node to the root list.
* @param node The node being cut.
* @param parent The parent of the node being cut.
* @param minNode The minimum node in the root list.
* @return The heap's new minimum node.
*/
private _cut(node: Node<K, V>, parent: Node<K, V>, minNode: Node<K, V>): Node<K, V> | null {
node.parent = null;
parent.degree--;
if (node.next === node) {
parent.child = null;
} else {
parent.child = node.next;
}
this._removeNodeFromList(node);
const newMinNode = this._mergeLists(minNode, node);
node.isMarked = false;
return newMinNode;
}
/**
* Perform a cascading cut on a node; mark the node if it is not marked,
* otherwise cut the node and perform a cascading cut on its parent.
* @param node The node being considered to be cut.
* @param minNode The minimum node in the root list.
* @return The heap's new minimum node.
*/
private _cascadingCut(node: Node<K, V>, minNode: Node<K, V> | null): Node<K, V> | null {
const parent = node.parent;
if (parent) {
if (node.isMarked) {
minNode = this._cut(node, parent, <Node<K, V>>minNode);
minNode = this._cascadingCut(parent, minNode);
} else {
node.isMarked = true;
}
}
return minNode;
}
/**
* Merge all trees of the same order together until there are no two trees of
* the same order.
* @param minNode The current minimum node.
* @return The new minimum node.
*/
private _consolidate(minNode: Node<K, V>): Node<K, V> | null {
const aux = [];
const it = new NodeListIterator<K, V>(minNode);
while (it.hasNext()) {
let current = it.next();
// If there exists another node with the same degree, merge them
let auxCurrent = aux[current.degree];
while (auxCurrent) {
if (this._compare(current, auxCurrent) > 0) {
const temp = current;
current = auxCurrent;
auxCurrent = temp;
}
this._linkHeaps(auxCurrent, current);
aux[current.degree] = null;
current.degree++;
auxCurrent = aux[current.degree];
}
aux[current.degree] = current;
}
let newMinNode = null;
for (let i = 0; i < aux.length; i++) {
const node = aux[i];
if (node) {
// Remove siblings before merging
node.next = node;
node.prev = node;
newMinNode = this._mergeLists(newMinNode, node);
}
}
return newMinNode;
}
/**
* Removes a node from a node list.
* @param node The node to remove.
*/
private _removeNodeFromList(node: Node<K, V>): void {
const prev = node.prev;
const next = node.next;
prev.next = next;
next.prev = prev;
node.next = node;
node.prev = node;
}
/**
* Links two heaps of the same order together.
*
* @private
* @param max The heap with the larger root.
* @param min The heap with the smaller root.
*/
private _linkHeaps(max: Node<K, V>, min: Node<K, V>): void {
this._removeNodeFromList(max);
min.child = this._mergeLists(max, min.child);
max.parent = min;
max.isMarked = false;
}
/**
* Merge two lists of nodes together.
*
* @private
* @param a The first list to merge.
* @param b The second list to merge.
* @return The new minimum node from the two lists.
*/
private _mergeLists(a: Node<K, V> | null, b: Node<K, V> | null): Node<K, V> | null {
if (!a) {
if (!b) {
return null;
}
return b;
}
if (!b) {
return a;
}
const temp = a.next;
a.next = b.next;
a.next.prev = a;
b.next = temp;
b.next.prev = b;
return this._compare(a, b) < 0 ? a : b;
}
/**
* Gets the size of a node list.
* @param node A node within the node list.
* @return The size of the node list.
*/
private _getNodeListSize(node: Node<K, V>): number {
let count = 0;
let current = node;
do {
count++;
if (current.child) {
count += this._getNodeListSize(current.child);
}
current = current.next;
} while (current !== node);
return count;
}
}
// file: node.ts
import { INode } from '@tyriar/fibonacci-heap';
export class Node<K, V> implements INode<K, V> {
public key: K;
public value: V | undefined;
public prev: Node<K, V>;
public next: Node<K, V>;
public parent: Node<K, V> | null = null;
public child: Node<K, V> | null = null;
public degree: number = 0;
public isMarked: boolean = false;
constructor(key: K, value?: V) {
this.key = key;
this.value = value;
this.prev = this;
this.next = this;
}
}
// file: nodeListIterator.ts
import { Node } from './node';
export class NodeListIterator<K, V> {
private _index: number;
private _items: Node<K, V>[];
/**
* Creates an Iterator used to simplify the consolidate() method. It works by
* making a shallow copy of the nodes in the root list and iterating over the
* shallow copy instead of the source as the source will be modified.
* @param start A node from the root list.
*/
constructor(start: Node<K, V>) {
this._index = -1;
this._items = [];
let current = start;
do {
this._items.push(current);
current = current.next;
} while (start !== current);
}
/**
* @return Whether there is a next node in the iterator.
*/
public hasNext(): boolean {
return this._index < this._items.length - 1;
}
/**
* @return The next node.
*/
public next(): Node<K, V> {
return this._items[++this._index];
}
}
// file: fibonacci-heap.d.ts
declare module '@tyriar/fibonacci-heap' {
export type CompareFunction<K, V> = (a: INode<K, V>, b: INode<K, V>) => number;
export interface INode<K, V> {
key: K;
value?: V;
}
/**
* A Fibonacci heap data structure with a key and optional value.
*/
export class FibonacciHeap<K, V> {
/**
* Creates a new Fibonacci heap.
* @param compare A custom compare function.
*/
constructor(compare?: CompareFunction<K, V>);
/**
* Clears the heap's data, making it an empty heap.
*/
clear(): void;
/**
* Decreases a key of a node.
* @param node The node to decrease the key of.
* @param newKey The new key to assign to the node.
*/
decreaseKey(node: INode<K, V>, newKey: K): void
/**
* Deletes a node.
* @param node The node to delete.
*/
delete(node: INode<K, V>): void;
/**
* Extracts and returns the minimum node from the heap.
* @return The heap's minimum node or null if the heap is empty.
*/
extractMinimum(): INode<K, V> | null;
/**
* Returns the minimum node from the heap.
* @return The heap's minimum node or null if the heap is empty.
*/
findMinimum(): INode<K, V> | null;
/**
* Inserts a new key-value pair into the heap.
* @param key The key to insert.
* @param value The value to insert.
* @return node The inserted node.
*/
insert(key: K, value?: V): INode<K, V>;
/**
* @return Whether the heap is empty.
*/
isEmpty(): boolean;
/**
* @return The size of the heap.
*/
size(): number;
/**
* Joins another heap to this heap.
* @param other The other heap.
*/
union(other: FibonacciHeap<K, V>): void;
}
}References
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Fibonacci Heaps” in Introduction to Algorithms, 2nd ed., Cambridge, MA: The MIT Press, 2001, ch. 20, pp.476-497
Textbooks
Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.
