Module org.cicirello.core
Package org.cicirello.ds

Class FibonacciHeap<E>

java.lang.Object
org.cicirello.ds.FibonacciHeap<E>
Type Parameters:
E - The type of object contained in the FibonacciHeap.
All Implemented Interfaces:
Iterable<PriorityQueueNode.Integer<E>>, Collection<PriorityQueueNode.Integer<E>>, Queue<PriorityQueueNode.Integer<E>>, MergeablePriorityQueue<E,FibonacciHeap<E>>, PriorityQueue<E>, Copyable<FibonacciHeap<E>>
public final class FibonacciHeap<E> extends Object implements MergeablePriorityQueue<E,FibonacciHeap<E>>, Copyable<FibonacciHeap<E>>
An implementation of a Fibonacci Heap. An instance of a FibonacciHeap contains (element, priority) pairs, such that the elements are distinct. The priority values are of type int.

Origin: Fibonacci heaps were first introduced in the following article: M. L. Fredman and R. E. Tarjan (1987). Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM, 34(3): 596-615, July 1987.

Priority order: FibonacciHeap instances are created via factory methods with names beginning with create. The priority order depends upon the factory method used to create the FibonacciHeap. Methods named createMinHeap produce a min heap with priority order minimum-priority-first-out. Methods named createMaxHeap produce a max heap with priority order maximum-priority-first-out.

Distinctness: The Object.hashCode() and Object.equals(java.lang.Object) methods are used to enforce distinctness, so be sure that the class of the elements properly implements these methods, or else behavior is not guaranteed.

Creating instances: To create an instance, use one of the factory methods, such as with: 


 FibonacciHeap<String> pq = FibonacciHeap.createMinHeap();

Method runtimes: The asymptotic runtime of the methods of this class are as follows (where n is the current size of the heap and m is the size of a Collection parameter where relevant). Note that in many cases in this list, the runtimes are amortized time and not actual time (see a reference on Fibonacci heaps for details).

The amortized runtime of change(E, int) depends on the direction of change. If the priority is decreased for a min-heap or increased for a max-heap, the amortized runtime of change(E, int) is O(1); but if the priority is increased for a min-heap or decreased for a max-heap, then the amortized time of change(E, int) is O(lg n).

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    change(E element, int priority)
    Changes the priority of an element if the element is present in the priority queue, and otherwise adds the (element, priority) pair to the priority queue.
    void
    clear()
    Clears the priority queue, removing all elements.
    boolean
    contains(Object o)
    Checks if this priority queue contains a given element or an (element, priority) pair with a given element.
    boolean
    containsAll(Collection<?> c)
    Checks if this PriorityQueue contains all elements or (element, priority) pairs from a given Collection.
    FibonacciHeap<E>
    copy()
    Creates an identical copy of this object.
    static <E> FibonacciHeap<E>
    createMaxHeap()
    Creates an empty FibonacciHeap with maximum-priority-first-out priority order.
    static <E> FibonacciHeap<E>
    createMaxHeap(Collection<PriorityQueueNode.Integer<E>> initialElements)
    Creates a FibonacciHeap from a collection of (element, priority) pairs, with a maximum-priority-first-out priority order.
    static <E> FibonacciHeap<E>
    createMinHeap()
    Creates an empty FibonacciHeap with minimum-priority-first-out priority order.
    static <E> FibonacciHeap<E>
    createMinHeap(Collection<PriorityQueueNode.Integer<E>> initialElements)
    Creates a FibonacciHeap from a collection of (element, priority) pairs, with a minimum-priority-first-out priority order.
    boolean
    demote(E element, int priority)
    Demotes an element relative to priority order if the element is present in the priority queue.
    boolean
    equals(Object other)
    Checks if this heap is the same as another, including that they contain the same (element, priority) pairs as another, including the specific structure the heap, as well as that the priority order is the same.
    int
    hashCode()
    Computes a hashCode.
    boolean
    isEmpty()
    Checks if the priority queue is empty.
    Iterator<PriorityQueueNode.Integer<E>>
    iterator()
    Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).
    boolean
    merge(FibonacciHeap<E> other)
    Merges another priority queue into this one, adding all of its (element, priority) pairs.
    boolean
    offer(E element, int priority)
    Adds an (element, priority) pair to the priority queue with a specified priority.
    boolean
    offer(PriorityQueueNode.Integer<E> pair)
    Adds an (element, priority) pair to the priority queue.
    PriorityQueueNode.Integer<E>
    peek()
    Gets the next (element, priority) pair in priority order from this priority queue, without removing it.
    E
    peekElement()
    Gets the next element in priority order from this priority queue, without removing it.
    int
    peekPriority()
    Gets the priority of the next element in priority order in the priority queue.
    int
    peekPriority(E element)
    Gets the priority of a specified element if it is present in the priority queue.
    PriorityQueueNode.Integer<E>
    poll()
    Removes and returns the next (element, priority) pair in priority order from this priority queue.
    E
    pollElement()
    Removes and returns the next element in priority order from this priority queue.
    boolean
    promote(E element, int priority)
    Promotes an element relative to priority order if the element is present in the priority queue.
    boolean
    remove(Object o)
    Removes from this priority queue the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.
    boolean
    removeAll(Collection<?> c)
    Removes from this priority queue all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.
    boolean
    retainAll(Collection<?> c)
    Removes from this priority queue all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.
    int
    size()
    Gets the current size of the priority queue, which is the number of (element, value) pairs that it contains.
    Object[]
    toArray()
    Returns an array containing all of the (element, priority) pairs contained in the priority queue.
    <T> T[]
    toArray(T[] array)
    Returns an array containing all of the (element, priority) pairs contained in the priority queue.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.util.Collection

    parallelStream, removeIf, spliterator, stream, toArray

    Methods inherited from interface java.lang.Iterable

    forEach

    Methods inherited from interface org.cicirello.ds.PriorityQueue

    add, add, addAll, element, pollThenAdd, pollThenAdd, remove, removeElement

  • Method Details

    • copy

      public FibonacciHeap<E> copy()
      Description copied from interface: Copyable
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<E>
      Returns:
      an identical copy of this object.

    • createMinHeap

      public static <E> FibonacciHeap<E> createMinHeap()
      Creates an empty FibonacciHeap with minimum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the FibonacciHeap.
      Returns:
      an empty FibonacciHeap with a minimum-priority-first-out priority order

    • createMinHeap

      public static <E> FibonacciHeap<E> createMinHeap(Collection<PriorityQueueNode.Integer<E>> initialElements)
      Creates a FibonacciHeap from a collection of (element, priority) pairs, with a minimum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the FibonacciHeap.
      Parameters:
      initialElements - The initial collection of (element, priority) pairs.
      Returns:
      a FibonacciHeap with a minimum-priority-first-out priority order
      Throws:
      IllegalArgumentException - if more than one pair in initialElements contains the same element.

    • createMaxHeap

      public static <E> FibonacciHeap<E> createMaxHeap()
      Creates an empty FibonacciHeap with maximum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the FibonacciHeap.
      Returns:
      an empty FibonacciHeap with a maximum-priority-first-out priority order

    • createMaxHeap

      public static <E> FibonacciHeap<E> createMaxHeap(Collection<PriorityQueueNode.Integer<E>> initialElements)
      Creates a FibonacciHeap from a collection of (element, priority) pairs, with a maximum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the FibonacciHeap.
      Parameters:
      initialElements - The initial collection of (element, priority) pairs.
      Returns:
      a FibonacciHeap with a maximum-priority-first-out priority order
      Throws:
      IllegalArgumentException - if more than one pair in initialElements contains the same element.

    • change

      public boolean change(E element, int priority)
      Description copied from interface: PriorityQueue
      Changes the priority of an element if the element is present in the priority queue, and otherwise adds the (element, priority) pair to the priority queue.

      For those implementations that allow duplicate elements, this method changes the priority of only one element, without defining which is chosen when such duplicates exist.

      Specified by:
      change in interface PriorityQueue<E>
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the priority queue changed as a consequence of this method call.

    • clear

      public void clear()
      Description copied from interface: PriorityQueue
      Clears the priority queue, removing all elements.
      Specified by:
      clear in interface Collection<E>
      Specified by:
      clear in interface PriorityQueue<E>

    • contains

      public boolean contains(Object o)
      Description copied from interface: PriorityQueue
      Checks if this priority queue contains a given element or an (element, priority) pair with a given element.
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface PriorityQueue<E>
      Parameters:
      o - An element or (element, priority) pair to check for containment of the element.
      Returns:
      true if and only if this priority queue contains the element.

    • containsAll

      public boolean containsAll(Collection<?> c)
      Checks if this PriorityQueue contains all elements or (element, priority) pairs from a given Collection.
      Specified by:
      containsAll in interface Collection<E>
      Specified by:
      containsAll in interface PriorityQueue<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs to check for containment.
      Returns:
      true if and only if this PriorityQueue contains all of the elements or (element, priority) pairs in c.

    • demote

      public boolean demote(E element, int priority)
      Description copied from interface: PriorityQueue
      Demotes an element relative to priority order if the element is present in the priority queue. For a min-heap, demotion means increasing the element's priority, while for a max-heap, demotion means decreasing its priority. If the element is not in the priority queue, or if its new priority is not a demotion, then this method does nothing.

      For those implementations that allow duplicate elements, this method changes the priority of only one element, without defining which is chosen when such duplicates exist.

      Specified by:
      demote in interface PriorityQueue<E>
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the priority queue changed as a consequence of this method call.

    • equals

      public boolean equals(Object other)
      Checks if this heap is the same as another, including that they contain the same (element, priority) pairs as another, including the specific structure the heap, as well as that the priority order is the same.
      Specified by:
      equals in interface Collection<E>
      Overrides:
      equals in class Object
      Parameters:
      other - The other heap.
      Returns:
      true if and only if this and other contain the same (element, priority) pairs, with the same priority order.

    • hashCode

      public int hashCode()
      Computes a hashCode.
      Specified by:
      hashCode in interface Collection<E>
      Overrides:
      hashCode in class Object
      Returns:
      a hashCode

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: PriorityQueue
      Checks if the priority queue is empty.
      Specified by:
      isEmpty in interface Collection<E>
      Specified by:
      isEmpty in interface PriorityQueue<E>
      Returns:
      true if and only if it is empty

    • iterator

      public Iterator<PriorityQueueNode.Integer<E>> iterator()
      Description copied from interface: PriorityQueue
      Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface PriorityQueue<E>
      Returns:
      an iterator over the (element, priority) pairs

    • merge

      public boolean merge(FibonacciHeap<E> other)
      Merges another priority queue into this one, adding all of its (element, priority) pairs. This is a destructive operation with no guarantees to the state of the other priority queue upon completion. Additionally, some implementations of this method may assume that other and this do not share any elements, and the priority queue may become unstable if they do. The priority order of both priority queues must be the same (e.g., both minheaps or both maxheaps).
      Specified by:
      merge in interface MergeablePriorityQueue<E,FibonacciHeap<E>>
      Parameters:
      other - The priority queue that you want to merge into this. Implementations need not make any guarantees as to the state of other upon completion.
      Returns:
      true if and only if this priority queue changed as a result of the merge
      Throws:
      IllegalArgumentException - if this and other have different priority-order (e.g., one is a minheap while the other is a maxheap)

    • offer

      public boolean offer(E element, int priority)
      Description copied from interface: PriorityQueue
      Adds an (element, priority) pair to the priority queue with a specified priority.
      Specified by:
      offer in interface PriorityQueue<E>
      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added, and false otherwise such as for those implementations that enforce distinct elements. For those implementations that allow duplicate elements, this method should always return true.

    • offer

      public boolean offer(PriorityQueueNode.Integer<E> pair)
      Description copied from interface: PriorityQueue
      Adds an (element, priority) pair to the priority queue.
      Specified by:
      offer in interface PriorityQueue<E>
      Specified by:
      offer in interface Queue<E>
      Parameters:
      pair - The (element, priority) pair to add.
      Returns:
      true if the (element, priority) pair was added, and false otherwise such as for those implementations that enforce distinct elements. For those implementations that allow duplicate elements, this method should always return true.

    • peekElement

      public E peekElement()
      Description copied from interface: PriorityQueue
      Gets the next element in priority order from this priority queue, without removing it.
      Specified by:
      peekElement in interface PriorityQueue<E>
      Returns:
      the next element in priority order, or null if empty.

    • peek

      public PriorityQueueNode.Integer<E> peek()
      Description copied from interface: PriorityQueue
      Gets the next (element, priority) pair in priority order from this priority queue, without removing it.
      Specified by:
      peek in interface PriorityQueue<E>
      Specified by:
      peek in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order, or null if empty.

    • peekPriority

      public int peekPriority()
      Description copied from interface: PriorityQueue
      Gets the priority of the next element in priority order in the priority queue.
      Specified by:
      peekPriority in interface PriorityQueue<E>
      Returns:
      the priority of the next element in priority order.

    • peekPriority

      public int peekPriority(E element)
      Description copied from interface: PriorityQueue
      Gets the priority of a specified element if it is present in the priority queue. This interface does not define the behavior when the element is not present. Implementations may define the behavior when the element is not present.

      For those implementations that allow duplicate elements, it returns the priority of any one of them, without defining which is chosen.

      Specified by:
      peekPriority in interface PriorityQueue<E>
      Parameters:
      element - The element whose priority is returned.
      Returns:
      the priority of a specified element.

    • pollElement

      public E pollElement()
      Description copied from interface: PriorityQueue
      Removes and returns the next element in priority order from this priority queue.
      Specified by:
      pollElement in interface PriorityQueue<E>
      Returns:
      the next element in priority order, or null if empty.

    • poll

      public PriorityQueueNode.Integer<E> poll()
      Description copied from interface: PriorityQueue
      Removes and returns the next (element, priority) pair in priority order from this priority queue.
      Specified by:
      poll in interface PriorityQueue<E>
      Specified by:
      poll in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order, or null if empty.

    • promote

      public boolean promote(E element, int priority)
      Description copied from interface: PriorityQueue
      Promotes an element relative to priority order if the element is present in the priority queue. For a min-heap, promotion means decreasing the element's priority, while for a max-heap, promotion means increasing its priority. If the element is not in the priority queue, or if its new priority is not a promotion, then this method does nothing.

      For those implementations that allow duplicate elements, this method changes the priority of only one element, without defining which is chosen when such duplicates exist.

      Specified by:
      promote in interface PriorityQueue<E>
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the priority queue changed as a consequence of this method call.

    • remove

      public boolean remove(Object o)
      Description copied from interface: PriorityQueue
      Removes from this priority queue the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.

      For those implementations that allow duplicate elements, this method removes only one element, without defining which is chosen when such duplicates exist.

      Specified by:
      remove in interface Collection<E>
      Specified by:
      remove in interface PriorityQueue<E>
      Parameters:
      o - An element or (element, priority) pair, such that element designates the desired pair to remove (note that if you pass an (element, priority) pair, only the element must match to cause removal.
      Returns:
      true if and only if an (element, priority) pair was removed as a result of this method call.

    • removeAll

      public boolean removeAll(Collection<?> c)
      Removes from this priority queue all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.

      The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling remove repeatedly.

      Specified by:
      removeAll in interface Collection<E>
      Specified by:
      removeAll in interface PriorityQueue<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs for removal.
      Returns:
      true if and only if this priority queue changed as a result of this method.

    • retainAll

      public boolean retainAll(Collection<?> c)
      Removes from this priority queue all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.

      The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling remove repeatedly.

      Specified by:
      retainAll in interface Collection<E>
      Specified by:
      retainAll in interface PriorityQueue<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs to keep.
      Returns:
      true if and only if this priority queue changed as a result of this method.

    • size

      public int size()
      Description copied from interface: PriorityQueue
      Gets the current size of the priority queue, which is the number of (element, value) pairs that it contains.
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface PriorityQueue<E>
      Returns:
      the current size of the priority queue.

    • toArray

      public Object[] toArray()
      Description copied from interface: PriorityQueue
      Returns an array containing all of the (element, priority) pairs contained in the priority queue. The order is not guaranteed. The runtime component type is Object. The priority queue does not maintain any references to the array that is returned, instead creating a new array upon each call to the toArray method. The length of the array that is returned is equal to the current PriorityQueue.size() of the priority queue.
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface PriorityQueue<E>
      Returns:
      an array, whose runtime component type is Object, containing all of the (element, priority) pairs currently in the priority queue.

    • toArray

      public <T> T[] toArray(T[] array)
      Returns an array containing all of the (element, priority) pairs contained in the priority queue. The order is not guaranteed. The runtime component type is the same as the array passed to it as a parameter. If the specified array is large enough, then it is used, otherwise a new array is allocated whose length is equal to the current PriorityQueue.size() of the priority queue. If the specified array is larger than the current size() of the priority queue, the first extra cell is set to null.
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface PriorityQueue<E>
      Type Parameters:
      T - The component type of the array to contain the (element, priority) pairs
      Parameters:
      array - The array in which to place the (element, priority) pairs, if it is sufficiently large, otherwise a new array of length PriorityQueue.size() is allocated of the same runtime type as array.
      Returns:
      The array in which the (element, priority) pairs have been inserted.
      Throws:
      ArrayStoreException - if the runtime component type of array is not compatible with the type of the (element, priority) pairs.
      NullPointerException - if array is null