 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 singlesource 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 TypeMethodDescriptionboolean
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
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 minheap, demotion means increasing the element's priority, while for a maxheap, 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 minheap, promotion means decreasing the element's priority, while for a maxheap, 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.
