org.apache.hadoop.util

类 PriorityQueue<T>

java.lang.Object

org.apache.hadoop.util.PriorityQueue<T>

public abstract class PriorityQueue<T>
extends Object

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.

构造器概要

构造器

构造器和说明
PriorityQueue()

方法概要

方法

限定符和类型	方法和说明
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.

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

构造器详细资料

PriorityQueue

public PriorityQueue()

方法详细资料

lessThan

protected abstract boolean lessThan(Object a,
               Object b)

Determines the ordering of objects in this priority queue. Subclasses must define this one method.

initialize

protected final void initialize(int maxSize)

Subclass constructors must call this.

put

public final void put(T 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.

insert

public 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()).

参数:

element -

返回:

true if element is added, false otherwise.

top

public final T top()

Returns the least element of the PriorityQueue in constant time.

pop

public final T pop()

Removes and returns the least element of the PriorityQueue in log(size) 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); }
 

size

public final int size()

Returns the number of elements currently stored in the PriorityQueue.

clear

public final void clear()

Removes all entries from the PriorityQueue.