lu.cs.co.util
Class PriorityQueue

java.lang.Object
  |
  +--lu.cs.co.util.PriorityQueue

public class PriorityQueue

extends Object

A priority queue. The elements of the queue must implement the Comparable interface of java.lang. The priority is given by the ordering induced by the compareTo method. It is required that all elements in the queue can be compared by this method. Note that the smaller objects (with respect to the ordering induced by the compareTo method) have lower priority, and that the findMin() and deleteMin() methods return the lowest priority element. To insert objects that do not implement the Comparable interface (or to insert such elements with a different ordering), use the class ObjectWithPriority.

See Also:

Comparable

Constructor Summary

PriorityQueue()
Constructs an empty queue.

PriorityQueue(int n)
Constructs an empty queue.

Method Summary

Object	deleteMin() Removes the lowest priority element of the queue.
Object	findMin() Return the lowest priority element in the queue.
void	insert(Comparable x) Insert an element into the queue.
boolean	isEmpty() Return true iff this queue is empty
int	size() Returns queue's size (number of elements).
void	toss(Comparable x) Insert an element into the queue.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PriorityQueue

public PriorityQueue(int n)

Constructs an empty queue.

Parameters:

n - a reasonable upper bound on the queue's size (the queue will increase its capacity automatically if this bound is violated, but starting with a good bound improves performance)

PriorityQueue

public PriorityQueue()

Constructs an empty queue.

Method Detail

size

public int size()

Returns queue's size (number of elements).

Returns:

the size of this queue

isEmpty

public boolean isEmpty()

Return true iff this queue is empty

Returns:

true if and only if this queue is empty

findMin

public Object findMin()

Return the lowest priority element in the queue. Runs in constant time if the queue is in heaporder.

Returns:

the smallest element

Throws:

UnderflowException - if the queue is empty

toss

public void toss(Comparable x)

Insert an element into the queue. Destroys heaporder. Runs in (amortised) constant time.

insert

public void insert(Comparable x)

Insert an element into the queue. Preserves heaporder. Runs in (amortised) logarithmic time in the heap's capacity.

deleteMin

public Object deleteMin()

Removes the lowest priority element of the queue. Works in constant time if the queue is in heaporder.

Returns:

the smallest element of the queue

Throws:

UnderflowException -