java.lang.Object | |
↳ | org.apache.lucene.util.PriorityQueue<T> |
Known Direct Subclasses |
A PriorityQueue maintains a partial ordering of its elements such that the least element can always be found in constant time. Put()'s and pop()'s require log(size) time.
NOTE: This class pre-allocates a full array of
length maxSize+1
, in initialize(int)
.
Fields | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
heap |
Public Constructors | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Public Methods | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Adds an Object to a PriorityQueue in log(size) time.
| |||||||||||
Removes all entries from the PriorityQueue.
| |||||||||||
Adds an Object to a PriorityQueue in log(size) time.
| |||||||||||
Removes and returns the least element of the PriorityQueue in log(size)
time.
| |||||||||||
Returns the number of elements currently stored in the PriorityQueue.
| |||||||||||
Returns the least element of the PriorityQueue in constant time.
| |||||||||||
Should be called when the Object at top changes values.
|
Protected Methods | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
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. | |||||||||||
Subclass constructors must call this.
| |||||||||||
Determines the ordering of objects in this priority queue.
|
[Expand]
Inherited Methods | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
From class
java.lang.Object
|
Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an ArrayIndexOutOfBoundsException is thrown.
Removes all entries from the PriorityQueue.
Adds an Object to a PriorityQueue in log(size) time. It returns the object (if any) that was dropped off the heap because it was full. This can be the given parameter (in case it is smaller than the full heap's minimum, and couldn't be added), or another object that was previously the smallest value in the heap and now has been replaced by a larger one, or null if the queue wasn't yet full with maxSize elements.
Removes and returns the least element of the PriorityQueue in log(size) time.
Returns the number of elements currently stored in the PriorityQueue.
Returns the least element of the PriorityQueue in constant time.
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.updateTop();instead of
o = pq.pop(); o.change(); pq.push(o);
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(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. Otherwise, the value returned will be used to
pre-populate the queue. Adds sentinel values to the queue.
If this method is extended to return a non-null value, then the following
usage pattern is recommended:
// extends getSentinelObject() to return a non-null value. PriorityQueueNOTE: if this method returns a non-null value, it will be called bypq = new MyQueue (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();
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.Subclass constructors must call this.
Determines the ordering of objects in this priority queue. Subclasses must define this one method.