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.hadoop.util
Class 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.

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

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

  Parameters:
    `element` -
  Returns:
    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.

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 © 2009 The Apache Software Foundation