Class PriorityQ<T>

  • Type Parameters:
    T - object type

    public final class PriorityQ<T>
    extends java.lang.Object
    Special-purpose priority queue. Does limited error checking and supports toss, buildHeap, poll, peek, percolateDown. It is faster than the equivalent class from java.util.
    Since:
    0.8.0
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) T[] a  
      (package private) java.util.Comparator<T> comp  
      (package private) int lastIndex  
    • Constructor Summary

      Constructors 
      Constructor Description
      PriorityQ​(int maxSize, java.util.Comparator<T> c)
      Construct a priority queue with a given capacity
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void buildHeap()
      build the heap...
      private int compare​(T a, T b)  
      boolean isEmpty()
      Check whether the heap is empty.
      T peek()
      Look at the top of the heap
      void percolateDown()
      Signals that the element on top of the heap has been updated
      private void percolateDown​(int i)  
      T poll()
      Remove the element on top of the heap
      int size()  
      void toss​(T t)
      Add an element at the end of the queue
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • a

        final T[] a
      • lastIndex

        int lastIndex
      • comp

        final java.util.Comparator<T> comp
    • Constructor Detail

      • PriorityQ

        public PriorityQ​(int maxSize,
                         java.util.Comparator<T> c)
        Construct a priority queue with a given capacity
        Parameters:
        maxSize - capacity
        c - comparator
    • Method Detail

      • size

        public int size()
        Returns:
        the size of the queue
      • compare

        private int compare​(T a,
                            T b)
      • toss

        public void toss​(T t)
        Add an element at the end of the queue
        Parameters:
        t - element to be added
      • peek

        public T peek()
        Look at the top of the heap
        Returns:
        the element on top
      • buildHeap

        public void buildHeap()
        build the heap...
      • percolateDown

        public void percolateDown()
        Signals that the element on top of the heap has been updated
      • percolateDown

        private void percolateDown​(int i)
      • poll

        public T poll()
        Remove the element on top of the heap
        Returns:
        the element being removed
      • isEmpty

        public boolean isEmpty()
        Check whether the heap is empty.
        Returns:
        true if empty