FileDocCategorySizeDatePackage
PriorityQueue.javaAPI DocApache Lucene 2.1.04316Wed Feb 14 10:46:42 GMT 2007org.apache.lucene.util

PriorityQueue

public abstract class PriorityQueue 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.

Fields Summary
private Object[]
heap
private int
size
private int
maxSize
Constructors Summary
Methods Summary
public final voidadjustTop()
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); }

    downHeap();
  
public final voidclear()
Removes all entries from the PriorityQueue.

    for (int i = 0; i <= size; i++)
      heap[i] = null;
    size = 0;
  
private final voiddownHeap()

    int i = 1;
    Object node = heap[i];			  // save top node
    int j = i << 1;				  // find smaller child
    int k = j + 1;
    if (k <= size && lessThan(heap[k], heap[j])) {
      j = k;
    }
    while (j <= size && lessThan(heap[j], node)) {
      heap[i] = heap[j];			  // shift up child
      i = j;
      j = i << 1;
      k = j + 1;
      if (k <= size && lessThan(heap[k], heap[j])) {
	j = k;
      }
    }
    heap[i] = node;				  // install saved node
  
protected final voidinitialize(int maxSize)
Subclass constructors must call this.

    size = 0;
    int heapSize = maxSize + 1;
    heap = new Object[heapSize];
    this.maxSize = maxSize;
  
public booleaninsert(java.lang.Object element)
Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).

param
element
return
true if element is added, false otherwise.

    if(size < maxSize){
      put(element);
      return true;
    }
    else if(size > 0 && !lessThan(element, top())){
      heap[1] = element;
      adjustTop();
      return true;
    }
    else
      return false;
   
protected abstract booleanlessThan(java.lang.Object a, java.lang.Object b)
Determines the ordering of objects in this priority queue. Subclasses must define this one method.

public final java.lang.Objectpop()
Removes and returns the least element of the PriorityQueue in log(size) time.

    if (size > 0) {
      Object result = heap[1];			  // save first value
      heap[1] = heap[size];			  // move last to first
      heap[size] = null;			  // permit GC of objects
      size--;
      downHeap();				  // adjust heap
      return result;
    } else
      return null;
  
public final voidput(java.lang.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++;
    heap[size] = element;
    upHeap();
  
public final intsize()
Returns the number of elements currently stored in the PriorityQueue.

    return size;
  
public final java.lang.Objecttop()
Returns the least element of the PriorityQueue in constant time.

    if (size > 0)
      return heap[1];
    else
      return null;
  
private final voidupHeap()

    int i = size;
    Object node = heap[i];			  // save bottom node
    int j = i >>> 1;
    while (j > 0 && lessThan(node, heap[j])) {
      heap[i] = heap[j];			  // shift parents down
      i = j;
      j = j >>> 1;
    }
    heap[i] = node;				  // install saved node