Interface IntPriorityQueueDouble

All Known Implementing Classes:
IntBinaryHeapDouble, IntFibonacciHeapDouble
public interface IntPriorityQueueDouble
Interface common to the classes that provide implementations of a priority queue of (element, priority) pairs, such that the elements are int values in the interval [0, n), and priorities are doubles. All IntPriorityQueueDouble implementations enforce distinct elements.

The purpose of such a priority queue implementation 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 priority queue, see the PriorityQueueDouble interface and the classes that implement it.

  • 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.
    void
    clear()
    Clears the IntPriorityQueueDouble, removing all elements.
    boolean
    contains(int element)
    Checks if an element is in the IntPriorityQueueDouble.
    boolean
    demote(int element, double priority)
    Demotes an element relative to priority order if the element is present in the IntPriorityQueueDouble.
    int
    domain()
    Returns the domain of this IntPriorityQueueDouble.
    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.
    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.
    int
    poll()
    Gets and removes the next element in priority order from this IntPriorityQueueDouble.
    default int
    pollThenOffer(int element, double priority)
    Performs a combination of a poll() and offer(int, double).
    boolean
    promote(int element, double priority)
    Promotes an element relative to priority order if the element is present in the IntPriorityQueueDouble.
    int
    size()
    Gets the current size of the IntPriorityQueueDouble, which is the number of (element, priority) pairs that it contains.
    int[]
    toArray()
    Creates and returns an array of the elements (only the elements without the priority values).

  • Method Details

    • change

      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.
      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

      void clear()
      Clears the IntPriorityQueueDouble, removing all elements.

    • contains

      boolean contains(int element)
      Checks if an element is in the 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.

    • demote

      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.
      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

      int domain()
      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.
      Returns:
      the domain of this IntPriorityQueueDouble

    • isEmpty

      boolean isEmpty()
      Checks if the IntPriorityQueueDouble is empty.
      Returns:
      true if and only if it is empty

    • offer

      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.
      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

      int peek()
      Gets the next element in priority order from this IntPriorityQueueDouble, without removing it. Behavior is undefined if it is empty.
      Returns:
      the next element in priority order.

    • peekPriority

      double peekPriority()
      Gets the priority of the next element in priority order in the IntPriorityQueueDouble. Behavior is undefined if it is empty.
      Returns:
      the priority of the next element in priority order.

    • peekPriority

      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.
      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.

    • poll

      int poll()
      Gets and removes the next element in priority order from this IntPriorityQueueDouble. Behavior is undefined if it is empty.
      Returns:
      the next element in priority order.

    • pollThenOffer

      default int pollThenOffer(int element, double priority)
      Performs a combination of a poll() and offer(int, double). The return value is undefined if the priority queue is empty at the time that this method is called. Thus, you should not call this method on empty priority queues. This method adds an (element, priority) pair to the IntPriorityQueueDouble with a specified priority, provided the element is not already in the IntPriorityQueueDouble. Unlike the offer(int, double) method, this method does not provide an explicit confirmation of success. If such confirmation is required, then you should instead directly use a combination of poll() and offer(int, double).

      The default implementation is equivalent to the following sequence of steps: int e = poll(); offer(element, priority); return e; Some priority queue classes may override this default behavior if they can do the combination of operations more efficiently than this sequence, such as the case for binary heap implementations.

      Parameters:
      element - The element to add.
      priority - The priority of the element.
      Returns:
      the next element in priority order. The return value is undefined if the priority queue is empty at the time that this method is called.
      Throws:
      IndexOutOfBoundsException - if element is negative, or if element is greater than or equal to the domain n.

    • promote

      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.
      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

      int size()
      Gets the current size of the IntPriorityQueueDouble, which is the number of (element, priority) pairs that it contains.
      Returns:
      the current size of the IntPriorityQueueDouble.

    • toArray

      int[] toArray()
      Creates and returns an array of the elements (only the elements without the priority values). The order of the elements is undefined, so may be in whatever order is most convenient to the implementation.
      Returns:
      an array of the elements