org.apache.lucene.util
Class PriorityQueue
public abstract class PriorityQueue
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.
void | adjustTop() - Should be called when the Object at top changes values.
|
void | clear() - Removes all entries from the PriorityQueue.
|
protected void | initialize(int maxSize) - Subclass constructors must call this.
|
boolean | insert(Object element) - Adds element to the PriorityQueue in log(size) time if either
the PriorityQueue is not full, or not lessThan(element, top()).
|
protected abstract boolean | lessThan(Object a, Object b) - Determines the ordering of objects in this priority queue.
|
Object | pop() - Removes and returns the least element of the PriorityQueue in log(size)
time.
|
void | put(Object element) - Adds an Object to a PriorityQueue in log(size) time.
|
int | size() - Returns the number of elements currently stored in the PriorityQueue.
|
Object | top() - Returns the least element of the PriorityQueue in constant 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); }
clear
public final void clear()
Removes all entries from the PriorityQueue.
initialize
protected final void initialize(int maxSize)
Subclass constructors must call this.
insert
public boolean insert(Object element)
Adds element to the PriorityQueue in log(size) time if either
the PriorityQueue is not full, or not lessThan(element, top()).
- true if element is added, false otherwise.
lessThan
protected abstract boolean lessThan(Object a,
Object b)
Determines the ordering of objects in this priority queue. Subclasses
must define this one method.
pop
public final Object pop()
Removes and returns the least element of the PriorityQueue in log(size)
time.
put
public final void put(Object element)
Adds an Object to a PriorityQueue in log(size) time.
If one tries to add more objects than maxSize from initialize
a RuntimeException (ArrayIndexOutOfBound) is thrown.
size
public final int size()
Returns the number of elements currently stored in the PriorityQueue.
top
public final Object top()
Returns the least element of the PriorityQueue in constant time.
Copyright © 2000-2006 Apache Software Foundation. All Rights Reserved.