All Packages  Class Hierarchy  This Package  Previous  Next  Index

Interface jdsl.core.api.PriorityQueue

public interface PriorityQueue
extends KeyBasedContainer
A priority queue is a partially-ordered container that allows for removal of the element with lowest (or highest, depending on the comparator used) priority. It does not specify any implementation; one implementation, however, is with a heap, which gives O(log N) time complexity for the two basic operations: insert(.) and removeMax().

The elements need to be comparable using whatever means the PQ has of making comparisons. If an element is not comparable, the priority queue will throw an InvalidElementException.

Version:
Sat Oct 25 22:49:41 EDT 1997
Author:
Mark Handy (mdh), Roberto Tamassia (rt)

Method Index

o insertItem(Object, Object)
Add a (key,element) pair to the set maintained by the priority queue, making whatever internal adjustments are necessary.
o min()
Allows access to element with first priority without removing it from the PriorityQueue.

o minElement()
Inspect the element (not the key) with first priority, without modifying the priority queue.
o minKey()
Inspect the key with first priority, without modifying the priority queue.
o removeMinElement()
Remove a (key,element) pair with first priority, making whatever internal adjustments are necessary.

Methods

o min 
 public abstract Locator min() throws EmptyContainerException
Allows access to element with first priority without removing it from the PriorityQueue.

Returns:
Locator to the element with first priority
Throws: EmptyContainerException
if the PriorityQueue is empty
o minElement 
 public abstract Object minElement() throws EmptyContainerException
Inspect the element (not the key) with first priority, without modifying the priority queue.

Returns:
The client element associated with a key of first priority
Throws: EmptyContainerException
if the PriorityQueue is empty
o minKey 
 public abstract Object minKey() throws EmptyContainerException
Inspect the key with first priority, without modifying the priority queue.

Returns:
A key of first priority among those in the priority queue
Throws: EmptyContainerException
if the PriorityQueue is empty
o insertItem 
 public abstract void insertItem(Object key,
                                 Object element) throws InvalidKeyException
Add a (key,element) pair to the set maintained by the priority queue, making whatever internal adjustments are necessary.

Parameters:
key - An object comparable under the implementation's comparison scheme
element - An arbitrary object the client associates with the key
o removeMinElement 
 public abstract Object removeMinElement() throws EmptyContainerException
Remove a (key,element) pair with first priority, making whatever internal adjustments are necessary.

Returns:
The client element (not the key) removed
Throws: EmptyContainerException
if the PriorityQueue is empty 
All Packages  Class Hierarchy  This Package  Previous  Next  Index