|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object org.apache.hadoop.util.PriorityQueue<T>
public abstract class PriorityQueue<T>
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.
Constructor Summary | |
---|---|
PriorityQueue()
|
Method Summary | |
---|---|
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(T 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. |
T |
pop()
Removes and returns the least element of the PriorityQueue in log(size) time. |
void |
put(T element)
Adds an Object to a 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. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public PriorityQueue()
Method Detail |
---|
protected abstract boolean lessThan(Object a, Object b)
protected final void initialize(int maxSize)
public final void put(T element)
public boolean insert(T element)
element
-
public final T top()
public final T pop()
public final void adjustTop()
{ pq.top().change(); pq.adjustTop(); }instead of
{ o = pq.pop(); o.change(); pq.push(o); }
public final int size()
public final void clear()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |