de.spieleck.util
Class PriorityQueue

java.lang.Object
  de.spieleck.util.PriorityQueue

public class PriorityQueue
extends java.lang.Object

A PriorityQueue maintains a partial ordering of its elements such that the least element can always be found in constant time.

This is achieved by a heap implementation, therefore Put()'s and pop()'s require log(size) time. Note that this heap is realized by linear insertion and not by "bubbling".

This class can either be directly used by passing a java.util.Comparator object to the constructor, or by subclassing and overriding the lessThan() method.

XXX This is an lazy implementation which spoils the very first entry in the heap!

Caution:This class is unsynchronized and therefore needs external synchronization in an multithreading environment.

Field Summary

protected java.lang.Object[]	heap
protected java.util.Comparator	myComp
protected int	size

Constructor Summary

PriorityQueue(int initialSize, java.util.Comparator comp)

Method Summary

void	adjustTop() Should be called when the Object at top changes values.
void	clear() Removes all entries from the PriorityQueue.
protected void	downHeap(int top) readjust top node in the heap to maintain heap condition.
int	getCapacity() Returns current capacity
int	getSize() Returns the number of elements currently stored in the PriorityQueue.
protected void	initialize(int initialSize) Subclass constructors must call this.
protected boolean	lessThan(java.lang.Object a, java.lang.Object b) Determines the ordering of objects in this priority queue.
java.lang.Object	pop() Removes and returns the least element of the PriorityQueue in log(size) time.
void	put(java.lang.Object element) Adds an Object to a PriorityQueue in log(size) time.
void	resort() Rearrange the heap, this is supposed to be O(n*log(n)) but better than nothing
void	setComparator(java.util.Comparator comp)
void	setTop(java.lang.Object element) Replace the topmost element.
java.lang.Object	top() Returns the least element of the PriorityQueue in constant time.
protected void	upHeap() readjust last node in the heap to maintain heap condition.

Methods inherited from class java.lang.Object

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

Field Detail

size

protected int size

heap

protected java.lang.Object[] heap

myComp

protected java.util.Comparator myComp

Constructor Detail

PriorityQueue

public PriorityQueue(int initialSize,
                     java.util.Comparator comp)

Method Detail

lessThan

protected boolean lessThan(java.lang.Object a,
                           java.lang.Object b)

Determines the ordering of objects in this priority queue. Subclasses can override this method.

setComparator

public void setComparator(java.util.Comparator comp)

initialize

protected final void initialize(int initialSize)

Subclass constructors must call this.

put

public final void put(java.lang.Object element)

Adds an Object to a PriorityQueue in log(size) time. Unless resize occurs ...

setTop

public final void setTop(java.lang.Object element)

Replace the topmost element.

top

public final java.lang.Object top()

Returns the least element of the PriorityQueue in constant time.

pop

public final java.lang.Object pop()

Removes and returns the least element of the PriorityQueue in log(size) time.

adjustTop

public final void adjustTop()

Should be called when the Object at top changes values. Still log(n) worst case, but it's at least twice as fast to

    { pq.top().change(); pq.adjustTop(); }
 

instead of

    { o = pq.pop(); o.change(); pq.push(o); }
 

getSize

public final int getSize()

Returns the number of elements currently stored in the PriorityQueue.

getCapacity

public final int getCapacity()

Returns current capacity

clear

public final void clear()

Removes all entries from the PriorityQueue.

resort

public void resort()

Rearrange the heap, this is supposed to be O(n*log(n)) but better than nothing

upHeap

protected final void upHeap()

readjust last node in the heap to maintain heap condition.

downHeap

protected final void downHeap(int top)

readjust top node in the heap to maintain heap condition.