Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.lucene.util
Class PriorityQueue

    java.lang.Object
      org.apache.lucene.util.PriorityQueue

Direct Known Subclasses:
  FieldSortedHitQueue, FuzzyQuery.ScoreTermQueue

    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.

Field Summary
`protected Object[]` | `heap`

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(Object element)` Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
`Object` | `insertWithOverflow(Object element)` insertWithOverflow() is the same as insert() except its return value: it returns the object (if any) that was dropped off the heap because it was full.
`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.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### heap

    protected Object[] heap

Constructor Detail

### PriorityQueue

    public PriorityQueue()

Method Detail

### 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(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.

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

  Parameters:
    `element` -
  Returns:
    true if element is added, false otherwise.

### insertWithOverflow

    public Object insertWithOverflow(Object element)

  insertWithOverflow() is the same as insert() except its return value: 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.

### top

    public final Object top()

  Returns the least element of the PriorityQueue in constant time.

### pop

    public final Object 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.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2000-2008 Apache Software Foundation. All Rights Reserved.