Package minpq

Interface ExtrinsicMinPQ<T>

Type Parameters:

T - the type of elements in this priority queue.

All Known Implementing Classes:

DoubleMapMinPQ, HeapMinPQ, OptimizedHeapMinPQ, UnsortedArrayMinPQ

public interface ExtrinsicMinPQ<T>

Priority queue where objects have extrinsic priority. While PriorityQueue relies on objects' Comparable (or a Comparator object), this interface requires priority values represented as double. Cannot contain duplicate or null items.

See Also:

DoubleMapMinPQ, UnsortedArrayMinPQ, HeapMinPQ, OptimizedHeapMinPQ

Method Summary

Modifier and Type	Method	Description
void	add(T item, double priority)	Adds an item with the given priority value.
void	changePriority(T item, double priority)	Updates the given items' associated priority value.
boolean	contains(T item)	Returns true if the given item is in this priority queue.
default boolean	isEmpty()	Returns true if this priority queue contains no items.
T	peekMin()	Returns the item with the minimum priority value.
T	removeMin()	Returns and removes the item with the minimum priority value.
int	size()	Returns the number of items in this priority queue.

Method Detail

add

void add(T item,
         double priority)

Adds an item with the given priority value.

Parameters:

item - the element to add.

priority - the priority value for the item.

Throws:

IllegalArgumentException - if item is null or already present.

contains

boolean contains(T item)

Returns true if the given item is in this priority queue.

Parameters:

item - element to be checked for containment.

Returns:

true if the given item is in this priority queue.

peekMin

T peekMin()

Returns the item with the minimum priority value.

Returns:

the item with the minimum priority value.

Throws:

NoSuchElementException - if this priority queue is empty.

removeMin

T removeMin()

Returns and removes the item with the minimum priority value.

Returns:

the item with the minimum priority value.

Throws:

NoSuchElementException - if this priority queue is empty.

changePriority

void changePriority(T item,
                    double priority)

Updates the given items' associated priority value.

Parameters:

item - the element whose associated priority value should be modified.

priority - the updated priority value.

Throws:

NoSuchElementException - if the item is not present.

size

int size()

Returns the number of items in this priority queue.

Returns:

the number of elements in this priority queue.

isEmpty

default boolean isEmpty()

Returns true if this priority queue contains no items.

Returns:

true if this priority queue contains no items.