brutil
Class PriorityQueueHeap

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

public class PriorityQueueHeap

extends java.lang.Object

PriorityQueue.java Created: Wed Sep 25 16:04:47 2002

Constructor Summary

PriorityQueueHeap()

Method Summary

boolean	decreaseKey(HandlePQ h, int newKey) Look at the (key, value) pair referenced by Handle h.
HandlePQ	extractMin() Extract the (key, value) pair associated with the smallest key in the queue and return its "value" object.
void	heapify(int i) Recusive method that maintains the heap property of the priority queue
HandlePQ	insert(int key, java.lang.Object obj) Insert a pair (key, obj) 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

PriorityQueueHeap

public PriorityQueueHeap()

Method Detail

insert

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

Insert a pair (key, obj) 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

obj - the object to be stored in the queue

Returns:

the wrapper object the holds the key and the object values

heapify

public void heapify(int i)

Recusive method that maintains the heap property of the priority queue

Parameters:

i - the index of the element to check the heap property

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.

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

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