brutil
Class PriorityQueueHeapArray

java.lang.Object
  |
  +--brutil.PriorityQueueHeapArray

public class PriorityQueueHeapArray

extends java.lang.Object

Constructor Summary

PriorityQueueHeapArray()

Method Summary

boolean	decreaseKey(HandlePQ h, int newkey) Look at the (key, value) pair referenced by Handle h.
void	doubleArray(int counter) Doubles the array size
HandlePQ	extractMin() Extract the (key, value) pair associated with the smallest key in the queue and return its "value" object.
int	handleGetKey(HandlePQ h) Get the key of the (key, value) pair associated with a given Handle.
java.lang.Object	handleGetValue(HandlePQ h) Get the value object of the (key, value) pair associated with a given Handle.
HandlePQ	insert(int key, java.lang.Object value) Insert a pair (key, value) into the queue, and return a Handle to this pair so that we can find it later in constant time.
boolean	isEmpty() Return true if there are no elements in the Priority Queue
HandlePQ	min() Return the HandlePQ object with the smallest key in the queue.
java.lang.String	toString() Returns all the elements in the PriorityQueue

Methods inherited from class java.lang.Object

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

Constructor Detail

PriorityQueueHeapArray

public PriorityQueueHeapArray()

Method Detail

insert

public HandlePQ insert(int key,
                       java.lang.Object value)

Insert a pair (key, value) into the queue, and return a Handle to this pair so that we can find it later in constant time.

Parameters:

key - the key value of the object

value - the object to be stored in the queue

Returns:

the wrapper object the holds the key and the object values

min

public HandlePQ min()

Return the HandlePQ object with the smallest key in the queue.

Returns:

the object with the smallest key value in the queue

extractMin

public HandlePQ extractMin()

Extract the (key, value) pair associated with the smallest key in the queue and return its "value" object.

Returns:

the wrapper object with the smallest key value

decreaseKey

public boolean decreaseKey(HandlePQ h,
                           int newkey)

Look at the (key, value) pair referenced by Handle h. If that pair is no longer in the queue, or its key is <= newkey, do nothing and return false. Otherwise, replace "key" by "newkey", fixup the queue, and return true.

Parameters:

h - the HandlePQ whose key value needs to be modified

newKey - the new value

Returns:

true if the key value was changes successfuly, false if the key value was not decreased.

handleGetKey

public int handleGetKey(HandlePQ h)

Get the key of the (key, value) pair associated with a given Handle.

Parameters:

h - the handlePQ object whose key value is needed

Returns:

the key value of the passed in HandlePQ object

handleGetValue

public java.lang.Object handleGetValue(HandlePQ h)

Get the value object of the (key, value) pair associated with a given Handle.

Parameters:

h - the HandlePQ wrapper object that holds the inserted object

Returns:

object value inside the HandlePQ wrapper object

doubleArray

public void doubleArray(int counter)

Doubles the array size

isEmpty

public boolean isEmpty()

Return true if there are no elements in the Priority Queue

Returns:

true if there are no elements in the Priority Queue

toString

public java.lang.String toString()

Returns all the elements in the PriorityQueue

Overrides:

toString in class java.lang.Object

Returns:

string value of all the elements in the queue