ap
Class HeapPriorityQueue

java.lang.Object
  ap.HeapPriorityQueue

All Implemented Interfaces:

PriorityQueue

public class HeapPriorityQueue

extends java.lang.Object

implements PriorityQueue

This class implements the PriorityQueue interface using a binary heap. For algorithmic and data structure details see Mark Weiss' Data Structures and Problem Solving with Java, Addison Wesley.

This class supports (n = # items stored in priority queue)

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

Implementation concepts borrowed from Mark Weiss; the basic idea is that the node whose index is k has children stored with indexes 2*k and 2*k+1 for left/right children, respectively. The root of the binary heap has index 1.

Constructor Summary

HeapPriorityQueue()
Constructs an 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

HeapPriorityQueue

public HeapPriorityQueue()

Constructs an 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.