Class IntFibonacciHeap

java.lang.Object
org.cicirello.ds.IntFibonacciHeap
All Implemented Interfaces:
IntPriorityQueue, Copyable<IntFibonacciHeap>

public class IntFibonacciHeap extends Object implements IntPriorityQueue, Copyable<IntFibonacciHeap>
An implementation of a Fibonacci Heap of (element, priority) pairs, such that the elements are distinct integers in the interval [0, n), and with priority values 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: IntFibonacciHeap instances are created via factory methods with names beginning with create. The priority order depends upon the factory method used to create the IntFibonacciHeap. 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.

Creating instances: To create an instance, use one of the factory methods. In this example an IntFibonacciHeap with an element domain of [0,100) is created:


 IntFibonacciHeap<String> pq = IntFibonacciHeap.createMinHeap(100);
 

In the above example, the element domain is [0,100) and the IntFibonacciHeap is initially empty.

Purpose: The purpose of such an IntFibonacciHeap is to support implementations of algorithms that require such a specialized case. For example, some graph algorithms such as Dijkstra's algorithm for single-source shortest paths, and Prim's algorithm for minimum spanning tree, rely on a priority queue of the vertex ids, which are usually ints in some finite range. Although such applications could use the classes that instead implement the PriorityQueue interface, using Java's wrapper type Integer, the classes that implement IntPriorityQueue that specialize the element type to int are optimized for this special case.

For a more general purpose binary heap, see the FibonacciHeap class.

Method runtimes: The asymptotic runtime of the methods of this class are as follows (where n is the current size of the heap). 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(int,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(int,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(int,int) is O(lg n).

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    change(int element, int priority)
    Changes the priority of an element if the element is present in the IntPriorityQueue, and otherwise adds the (element, priority) pair to the IntPriorityQueue.
    final void
    Clears the IntPriorityQueue, removing all elements.
    final boolean
    contains(int element)
    Checks if an element is in the IntPriorityQueue.
    Creates an identical copy of this object.
    Initializes an empty max-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
    Initializes an empty min-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
    boolean
    demote(int element, int priority)
    Demotes an element relative to priority order if the element is present in the IntPriorityQueue.
    final int
    Returns the domain of this IntPriorityQueue.
    final boolean
    Checks if the IntPriorityQueue is empty.
    boolean
    offer(int element, int priority)
    Adds an (element, priority) pair to the IntPriorityQueue with a specified priority, provided the element is not already in the IntPriorityQueue.
    final int
    Gets the next element in priority order from this IntPriorityQueue, without removing it.
    int
    Gets the priority of the next element in priority order in the IntPriorityQueue.
    int
    peekPriority(int element)
    Gets the current priority of a specified element in the IntPriorityQueue.
    final int
    Gets and removes the next element in priority order from this IntPriorityQueue.
    boolean
    promote(int element, int priority)
    Promotes an element relative to priority order if the element is present in the IntPriorityQueue.
    final int
    Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Method Details

    • copy

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

      public boolean change(int element, int priority)
      Changes the priority of an element if the element is present in the IntPriorityQueue, and otherwise adds the (element, priority) pair to the IntPriorityQueue.
      Specified by:
      change in interface IntPriorityQueue
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueue changed as a consequence of this method call.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.
    • clear

      public final void clear()
      Description copied from interface: IntPriorityQueue
      Clears the IntPriorityQueue, removing all elements.
      Specified by:
      clear in interface IntPriorityQueue
    • contains

      public final boolean contains(int element)
      Checks if an element is in the IntPriorityQueue.
      Specified by:
      contains in interface IntPriorityQueue
      Parameters:
      element - The element to check for containment.
      Returns:
      true if and only if there exists an (element, priority) pair for the specified element.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.
    • createMaxHeap

      public static IntFibonacciHeap createMaxHeap(int n)
      Initializes an empty max-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
      Parameters:
      n - The size of the domain of the elements of the max-heap.
      Returns:
      an empty max-heap
      Throws:
      IllegalArgumentException - if n is non-positive
    • createMinHeap

      public static IntFibonacciHeap createMinHeap(int n)
      Initializes an empty min-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).
      Parameters:
      n - The size of the domain of the elements of the min-heap.
      Returns:
      an empty min-heap
      Throws:
      IllegalArgumentException - if n is non-positive
    • demote

      public boolean demote(int element, int priority)
      Demotes an element relative to priority order if the element is present in the IntPriorityQueue. 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 IntPriorityQueue, or if its new priority is not a demotion, then this method does nothing.
      Specified by:
      demote in interface IntPriorityQueue
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueue changed as a consequence of this method call.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.
    • domain

      public final int domain()
      Description copied from interface: IntPriorityQueue
      Returns the domain of this IntPriorityQueue. Note that the domain is not the same thing as the size. The domain defines the elements that are allowed in the IntPriorityQueue, whether or not they actually appear within it.
      Specified by:
      domain in interface IntPriorityQueue
      Returns:
      the domain of this IntPriorityQueue
    • isEmpty

      public final boolean isEmpty()
      Description copied from interface: IntPriorityQueue
      Checks if the IntPriorityQueue is empty.
      Specified by:
      isEmpty in interface IntPriorityQueue
      Returns:
      true if and only if it is empty
    • offer

      public boolean offer(int element, int priority)
      Adds an (element, priority) pair to the IntPriorityQueue with a specified priority, provided the element is not already in the IntPriorityQueue.
      Specified by:
      offer in interface IntPriorityQueue
      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added, and false if the IntPriorityQueue already contained the element.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.
    • peek

      public final int peek()
      Gets the next element in priority order from this IntPriorityQueue, without removing it. Behavior is undefined if it is empty.
      Specified by:
      peek in interface IntPriorityQueue
      Returns:
      the next element in priority order.
      Throws:
      NullPointerException - if empty
    • peekPriority

      public int peekPriority()
      Gets the priority of the next element in priority order in the IntPriorityQueue. Behavior is undefined if it is empty.
      Specified by:
      peekPriority in interface IntPriorityQueue
      Returns:
      the priority of the next element in priority order.
      Throws:
      NullPointerException - if empty
    • peekPriority

      public int peekPriority(int element)
      Gets the current priority of a specified element in the IntPriorityQueue. Behavior is undefined if the IntPriorityQueue doesn't contain the element.
      Specified by:
      peekPriority in interface IntPriorityQueue
      Parameters:
      element - the element whose priority is returned
      Returns:
      the current priority of element.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n. * @throws NullPointerException if element is not in the heap
    • poll

      public final int poll()
      Description copied from interface: IntPriorityQueue
      Gets and removes the next element in priority order from this IntPriorityQueue. Behavior is undefined if it is empty.
      Specified by:
      poll in interface IntPriorityQueue
      Returns:
      the next element in priority order.
    • promote

      public boolean promote(int element, int priority)
      Promotes an element relative to priority order if the element is present in the IntPriorityQueue. 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 IntPriorityQueue, or if its new priority is not a promotion, then this method does nothing.
      Specified by:
      promote in interface IntPriorityQueue
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueue changed as a consequence of this method call.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.
    • size

      public final int size()
      Description copied from interface: IntPriorityQueue
      Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.
      Specified by:
      size in interface IntPriorityQueue
      Returns:
      the current size of the IntPriorityQueue.