public abstract class PriorityQueue
extends java.lang.Object
NOTE: This class pre-allocates a full array of
length maxSize+1
, in initialize(int)
.
Modifier and Type | Field and Description |
---|---|
protected java.lang.Object[] |
heap |
Constructor and Description |
---|
PriorityQueue() |
Modifier and Type | Method and Description |
---|---|
java.lang.Object |
add(java.lang.Object element)
Adds an Object to a PriorityQueue in log(size) time.
|
void |
adjustTop()
Deprecated.
use
updateTop() which returns the new top element and
saves an additional call to top() . |
void |
clear()
Removes all entries from the PriorityQueue.
|
protected java.lang.Object |
getSentinelObject()
This method can be overridden by extending classes to return a sentinel
object which will be used by
initialize(int) 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(Object, Object) should always favor the
non-sentinel values).By default, this method returns false, which means the queue will not be filled with sentinel values. |
protected void |
initialize(int maxSize)
Subclass constructors must call this.
|
boolean |
insert(java.lang.Object element)
Deprecated.
use
insertWithOverflow(Object) instead, which
encourages objects reuse. |
java.lang.Object |
insertWithOverflow(java.lang.Object element)
insertWithOverflow() is the same as insert() except its
return value: it returns the object (if any) that was
dropped off the heap because it was full.
|
protected abstract 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)
Deprecated.
use
add(Object) which returns the new top object,
saving an additional call to top() . |
int |
size()
Returns the number of elements currently stored in the PriorityQueue.
|
java.lang.Object |
top()
Returns the least element of the PriorityQueue in constant time.
|
java.lang.Object |
updateTop()
Should be called when the Object at top changes values.
|
protected abstract boolean lessThan(java.lang.Object a, java.lang.Object b)
protected java.lang.Object getSentinelObject()
initialize(int)
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(Object, Object)
should always favor the
non-sentinel values).// extends getSentinelObject() to return a non-null value. PriorityQueue pq = new MyQueue(numHits); // save the 'top' element, which is guaranteed to not be null. MyObject pqTop = (MyObject) 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
initialize(int)
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.protected final void initialize(int maxSize)
public final void put(java.lang.Object element)
add(Object)
which returns the new top object,
saving an additional call to top()
.public final java.lang.Object add(java.lang.Object element)
ArrayIndexOutOfBoundsException
is thrown.public boolean insert(java.lang.Object element)
insertWithOverflow(Object)
instead, which
encourages objects reuse.element
- public java.lang.Object insertWithOverflow(java.lang.Object element)
public final java.lang.Object top()
public final java.lang.Object pop()
public final void adjustTop()
updateTop()
which returns the new top element and
saves an additional call to top()
.pq.top().change(); pq.adjustTop();instead of
o = pq.pop(); o.change(); pq.push(o);
public final java.lang.Object updateTop()
pq.top().change(); pq.updateTop();instead of
o = pq.pop(); o.change(); pq.push(o);
public final int size()
public final void clear()
Copyright © 2000-2018 Apache Software Foundation. All Rights Reserved.