com.kuka.graph.util
Interface PriorityQueue<E>

Type Parameters:

E - the type of elements held in this priority queue

All Known Implementing Classes:

PairingHeap

public interface PriorityQueue<E>

This priority queue interface is tailored for graph search algorithms. Its interface is different to a standard Java PriorityQueue to facilitate an efficient decreaseKey operation, which reduces the priority of a value that is already in the queue. Thus, handles are used to reference values in the heap

Nested Class Summary

static interface

PriorityQueue.Handle<T> Handle to elements in a priority queue for efficient access.

Method Summary

PriorityQueue.Handle<E>	add(E element) Adds an element to this priority queue, maintaining heap order.
void	clear() Removes all of the elements from this priority queue.
void	decreaseKey(PriorityQueue.Handle<E> handle, E element) Changes the value of the item stored in the pairing heap (optional operation).
PriorityQueue.Handle<E>	findMin() Finds and returns the item with the lowest priority in this queue.
boolean	isEmpty() Returns true if this priority queue contains no elements.
E	removeMin() Removes and returns the item with the lowest priority from this queue.
int	size() Returns the number of elements in this priority queue.

Method Detail

size

int size()

Returns the number of elements in this priority queue.

Returns:

the number of elements in this priority queue

isEmpty

boolean isEmpty()

Returns true if this priority queue contains no elements.

Returns:

true if this priority queue contains no elements

add

PriorityQueue.Handle<E> add(E element)

Adds an element to this priority queue, maintaining heap order. Duplicates are allowed.

Parameters:

element - the value of the item to insert

Returns:

a handle for modifying the priority of the element with decreaseKey(Handle, Object)

findMin

PriorityQueue.Handle<E> findMin()

Finds and returns the item with the lowest priority in this queue.

Returns:

the item with the lowest priority

Throws:

IllegalStateException - if this priority queue is empty

See Also:

removeMin()

removeMin

E removeMin()

Removes and returns the item with the lowest priority from this queue.

Returns:

the item with the lowest priority

Throws:

IllegalStateException - if this priority queue is empty

See Also:

findMin()

decreaseKey

void decreaseKey(PriorityQueue.Handle<E> handle,
                 E element)

Changes the value of the item stored in the pairing heap (optional operation).

The given handle must be valid. A handle is valid as long as it is an element of this priority queue. When the corresponding value is removed from the queue the handle is invalid. To check whether a handle is valid call PriorityQueue.Handle.isValid(). Note that this is considered an advanced operation and might not be supported by all priority queues.

Parameters:

handle - a valid handle returned by add(Object)

element - the new element, which must be smaller than the currently stored one

Throws:

IllegalArgumentException - if item is invalid

UnsupportedOperationException - if the decreaseKey operation is not supported by this priority queue

clear

void clear()

Removes all of the elements from this priority queue. The priority queue will be empty after this method returns.