public abstract class PriorityQueue<T> extends Object
NOTE: This class will pre-allocate a full array of
length maxSize+1
if instantiated via the
PriorityQueue(int,boolean)
constructor with
prepopulate
set to true
.
Constructor and Description |
---|
PriorityQueue(int maxSize) |
PriorityQueue(int maxSize,
boolean prepopulate) |
Modifier and Type | Method and Description |
---|---|
T |
add(T element)
Adds an Object to a PriorityQueue in log(size) time.
|
void |
clear()
Removes all entries from the PriorityQueue.
|
protected Object[] |
getHeapArray()
This method returns the internal heap array as Object[].
|
protected T |
getSentinelObject()
This method can be overridden by extending classes to return a sentinel
object which will be used by the
PriorityQueue(int,boolean)
constructor to fill the queue, so that the code which uses that queue can always
assume it's full and only change the top without attempting to insert any new
object.Those sentinel values should always compare worse than any non-sentinel value (i.e., lessThan(T, T) should always favor the
non-sentinel values).By default, this method returns false, which means the queue will not be filled with sentinel values. |
T |
insertWithOverflow(T element)
Adds an Object to a PriorityQueue in log(size) time.
|
protected abstract boolean |
lessThan(T a,
T b)
Determines the ordering of objects in this priority queue.
|
T |
pop()
Removes and returns the least element of the PriorityQueue in log(size)
time.
|
int |
size()
Returns the number of elements currently stored in the PriorityQueue.
|
T |
top()
Returns the least element of the PriorityQueue in constant time.
|
T |
updateTop()
Should be called when the Object at top changes values.
|
public PriorityQueue(int maxSize)
public PriorityQueue(int maxSize, boolean prepopulate)
protected abstract boolean lessThan(T a, T b)
true
iff parameter a is less than parameter b.protected T getSentinelObject()
PriorityQueue(int,boolean)
constructor to fill the queue, so that the code which uses that queue can always
assume it's full and only change the top without attempting to insert any new
object.lessThan(T, T)
should always favor the
non-sentinel values).// extends getSentinelObject() to return a non-null value. PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits); // save the 'top' element, which is guaranteed to not be null. MyObject pqTop = pq.top(); <...> // now in order to add a new element, which is 'better' than top (after // you've verified it is better), it is as simple as: pqTop.change(). pqTop = pq.updateTop();NOTE: if this method returns a non-null value, it will be called by the
PriorityQueue(int,boolean)
constructor
size()
times, relying on a new object to be returned and will not
check if it's null again. Therefore you should ensure any call to this
method creates a new instance and behaves consistently, e.g., it cannot
return null if it previously returned non-null.public final T add(T element)
ArrayIndexOutOfBoundsException
is thrown.public T insertWithOverflow(T element)
public final T top()
public final T pop()
public final T updateTop()
pq.top().change(); pq.updateTop();instead of
o = pq.pop(); o.change(); pq.push(o);
public final int size()
public final void clear()
protected final Object[] getHeapArray()
Copyright © 2000-2015 Apache Software Foundation. All Rights Reserved.