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

Interface IntPriorityQueue

All Known Implementing Classes:
IntBinaryHeap, IntFibonacciHeap
public interface IntPriorityQueue
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 also ints. All IntPriorityQueue 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 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 priority queue, see the PriorityQueue interface and the classes that implement it.

  • 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.
    void
    clear()
    Clears the IntPriorityQueue, removing all elements.
    boolean
    contains(int element)
    Checks if an element is in the IntPriorityQueue.
    boolean
    demote(int element, int priority)
    Demotes an element relative to priority order if the element is present in the IntPriorityQueue.
    int
    domain()
    Returns the domain of this IntPriorityQueue.
    boolean
    isEmpty()
    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.
    int
    peek()
    Gets the next element in priority order from this IntPriorityQueue, without removing it.
    int
    peekPriority()
    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.
    int
    poll()
    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.
    int
    size()
    Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.

  • Method Details

    • change

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

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

    • contains

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

    • demote

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

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

    • isEmpty

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

    • offer

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

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

    • peekPriority

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

    • peekPriority

      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.
      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 IntPriorityQueue. Behavior is undefined if it is empty.
      Returns:
      the next element in priority order.

    • promote

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

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