ap
Class ArrayPriorityQueue

java.lang.Object
  ap.ArrayPriorityQueue

All Implemented Interfaces:

PriorityQueue

public class ArrayPriorityQueue

extends java.lang.Object

implements PriorityQueue

A simple yet completely functional implementation of the PriorityQueue interface. The interface is part of the AP subset and is testable. This implementation is not part of the subset, but is useful in a classroom setting.

This class supports (n = # items stored in priority queue) PriorityQueue operations with the following complexities.

operation	worst case	average case
add	O(1)	O(1)
peekMin	O(n)	O(n)
removeMin	O(n)	O(n)

The underlying storage is java.util.ArrayList which supports constant time add (to end), but which requires linear search to find the smallest element.

This implementation is provided at apcentral.

Constructor Summary

ArrayPriorityQueue()
Constructs an initially empty priority queue.

Method Summary

void	add(java.lang.Object x) Adds an item to this priority queue.
boolean	isEmpty() Returns true if this stack is empty, otherwise returns false.
java.lang.Object	peekMin() Returns the smallest item stored in this priority queue without removing it.
java.lang.Object	removeMin() Removes and returns the smallest item stored in this priority queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayPriorityQueue

public ArrayPriorityQueue()

Constructs an initially empty priority queue.

Method Detail

add

public void add(java.lang.Object x)

Description copied from interface: PriorityQueue

Adds an item to this priority queue.

Specified by:

add in interface PriorityQueue

Parameters:

x - is the object added to this priority queue

removeMin

public java.lang.Object removeMin()

Description copied from interface: PriorityQueue

Removes and returns the smallest item stored in this priority queue.

Specified by:

removeMin in interface PriorityQueue

Returns:

the smallest item stored in this priority queue

peekMin

public java.lang.Object peekMin()

Description copied from interface: PriorityQueue

Returns the smallest item stored in this priority queue without removing it.

Specified by:

peekMin in interface PriorityQueue

Returns:

the smallest item stored in this priority queue

isEmpty

public boolean isEmpty()

Description copied from interface: PriorityQueue

Returns true if this stack is empty, otherwise returns false.

Specified by:

isEmpty in interface PriorityQueue

Returns:

true if this stack is empty, otherwise return false.