Package org.apache.hadoop.util

Class PriorityQueue<T>

java.lang.Object
org.apache.hadoop.util.PriorityQueue<T>
@Private @Unstable 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

    Constructors
    Constructor
    Description
    PriorityQueue()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    final void
    adjustTop()
    Should be called when the Object at top changes values.
    final void
    clear()
    Removes all entries from the PriorityQueue.
    protected final 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.
    final T
    pop()
    Removes and returns the least element of the PriorityQueue in log(size) time.
    final void
    put(T element)
    Adds an Object to a PriorityQueue in log(size) time.
    final int
    size()
    Returns the number of elements currently stored in the PriorityQueue.
    final 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 Details

    • PriorityQueue

      public PriorityQueue()

  • Method Details

    • lessThan

      protected abstract boolean lessThan(Object a, Object b)
      Determines the ordering of objects in this priority queue. Subclasses must define this one method.
      Parameters:
      a - object a.
      b - object b.
      Returns:
      if a less than b true, not false

    • initialize

      protected final void initialize(int maxSize)
      Subclass constructors must call this.
      Parameters:
      maxSize - max size.

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

    • 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 - element.
      Returns:
      true if element is added, false otherwise.

    • top

      public final T top()
      Returns the least element of the PriorityQueue in constant time.
      Returns:
      T Generics Type T.

    • pop

      public final T pop()
      Removes and returns the least element of the PriorityQueue in log(size) time.
      Returns:
      T Generics Type T.

    • 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.
      Returns:
      size.

    • clear

      public final void clear()
      Removes all entries from the PriorityQueue.