Growing with the Web

Fibonacci heap

Published , updated
Tags:

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.

Fibonacci heap

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.

The animations in this article rely on CSS transforms on SVG which is not yet implemented in Edge.

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.

The order of a Fibonacci heap depend on the number of children and branches it has
Some examples of trees of order 0, 1 and 2 (the black nodes are 'marked')

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.

Links of a Fibonacci heap

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.

Fibonacci heap find minimum operation example

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.

Fibonacci heap insert operation example

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.

Fibonacci heap union operation example, your browser doesn't support SVG.

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.

Fibonacci heap decrease key operation example, your browser doesn't support SVG.
DecreaseKey(20, 1)

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.

Fibonacci heap extract minimum operation example, your browser doesn't support SVG.

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.

Fibonacci heap extract minimum operation example, your browser doesn't support SVG.

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;

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.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!