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

Class IntFibonacciHeapDouble

java.lang.Object
org.cicirello.ds.IntFibonacciHeapDouble
All Implemented Interfaces:
IntPriorityQueueDouble, Copyable<IntFibonacciHeapDouble>
public class IntFibonacciHeapDouble extends Object implements IntPriorityQueueDouble, Copyable<IntFibonacciHeapDouble>
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 double.

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: IntFibonacciHeapDouble instances are created via factory methods with names beginning with create. The priority order depends upon the factory method used to create the IntFibonacciHeapDouble. 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 IntFibonacciHeapDouble with an element domain of [0,100) is created: 


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

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

Purpose: The purpose of such an IntFibonacciHeapDouble 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 PriorityQueueDouble interface, using Java's wrapper type Integer, the classes that implement IntPriorityQueueDouble that specialize the element type to int are optimized for this special case.

For a more general purpose binary heap, see the FibonacciHeapDouble 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,double) 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,double) 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,double) is O(lg n).

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    change(int element, double priority)
    Changes the priority of an element if the element is present in the IntPriorityQueueDouble, and otherwise adds the (element, priority) pair to the IntPriorityQueueDouble.
    final void
    clear()
    Clears the IntPriorityQueueDouble, removing all elements.
    final boolean
    contains(int element)
    Checks if an element is in the IntPriorityQueueDouble.
    IntFibonacciHeapDouble
    copy()
    Creates an identical copy of this object.
    static IntFibonacciHeapDouble
    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).
    static IntFibonacciHeapDouble
    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).
    boolean
    demote(int element, double priority)
    Demotes an element relative to priority order if the element is present in the IntPriorityQueueDouble.
    final int
    domain()
    Returns the domain of this IntPriorityQueueDouble.
    final boolean
    isEmpty()
    Checks if the IntPriorityQueueDouble is empty.
    boolean
    offer(int element, double priority)
    Adds an (element, priority) pair to the IntPriorityQueueDouble with a specified priority, provided the element is not already in the IntPriorityQueueDouble.
    final int
    peek()
    Gets the next element in priority order from this IntPriorityQueueDouble, without removing it.
    double
    peekPriority()
    Gets the priority of the next element in priority order in the IntPriorityQueueDouble.
    double
    peekPriority(int element)
    Gets the current priority of a specified element in the IntPriorityQueueDouble.
    final int
    poll()
    Gets and removes the next element in priority order from this IntPriorityQueueDouble.
    boolean
    promote(int element, double priority)
    Promotes an element relative to priority order if the element is present in the IntPriorityQueueDouble.
    final int
    size()
    Gets the current size of the IntPriorityQueueDouble, 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 IntFibonacciHeapDouble copy()
      Description copied from interface: Copyable
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<IntFibonacciHeapDouble>
      Returns:
      an identical copy of this object.

    • change

      public boolean change(int element, double priority)
      Changes the priority of an element if the element is present in the IntPriorityQueueDouble, and otherwise adds the (element, priority) pair to the IntPriorityQueueDouble.
      Specified by:
      change in interface IntPriorityQueueDouble
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueueDouble 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: IntPriorityQueueDouble
      Clears the IntPriorityQueueDouble, removing all elements.
      Specified by:
      clear in interface IntPriorityQueueDouble

    • contains

      public final boolean contains(int element)
      Checks if an element is in the IntPriorityQueueDouble.
      Specified by:
      contains in interface IntPriorityQueueDouble
      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 IntFibonacciHeapDouble 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 IntFibonacciHeapDouble 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, double priority)
      Demotes an element relative to priority order if the element is present in the IntPriorityQueueDouble. 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 IntPriorityQueueDouble, or if its new priority is not a demotion, then this method does nothing.
      Specified by:
      demote in interface IntPriorityQueueDouble
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueueDouble 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: IntPriorityQueueDouble
      Returns the domain of this IntPriorityQueueDouble. Note that the domain is not the same thing as the size. The domain defines the elements that are allowed in the IntPriorityQueueDouble, whether or not they actually appear within it.
      Specified by:
      domain in interface IntPriorityQueueDouble
      Returns:
      the domain of this IntPriorityQueueDouble

    • isEmpty

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

    • offer

      public boolean offer(int element, double priority)
      Adds an (element, priority) pair to the IntPriorityQueueDouble with a specified priority, provided the element is not already in the IntPriorityQueueDouble.
      Specified by:
      offer in interface IntPriorityQueueDouble
      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added, and false if the IntPriorityQueueDouble 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 IntPriorityQueueDouble, without removing it. Behavior is undefined if it is empty.
      Specified by:
      peek in interface IntPriorityQueueDouble
      Returns:
      the next element in priority order.
      Throws:
      NullPointerException - if empty

    • peekPriority

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

    • peekPriority

      public double peekPriority(int element)
      Gets the current priority of a specified element in the IntPriorityQueueDouble. Behavior is undefined if the IntPriorityQueueDouble doesn't contain the element.
      Specified by:
      peekPriority in interface IntPriorityQueueDouble
      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: IntPriorityQueueDouble
      Gets and removes the next element in priority order from this IntPriorityQueueDouble. Behavior is undefined if it is empty.
      Specified by:
      poll in interface IntPriorityQueueDouble
      Returns:
      the next element in priority order.

    • promote

      public boolean promote(int element, double priority)
      Promotes an element relative to priority order if the element is present in the IntPriorityQueueDouble. 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 IntPriorityQueueDouble, or if its new priority is not a promotion, then this method does nothing.
      Specified by:
      promote in interface IntPriorityQueueDouble
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the IntPriorityQueueDouble 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: IntPriorityQueueDouble
      Gets the current size of the IntPriorityQueueDouble, which is the number of (element, priority) pairs that it contains.
      Specified by:
      size in interface IntPriorityQueueDouble
      Returns:
      the current size of the IntPriorityQueueDouble.