Class PriorityQueue<T>


  • public class PriorityQueue<T>
    extends Object
    A priority queue where the items are ordered according to a specified comparator. This priority queue uses a binary heap algorithm as described in Mark Allen Weis, _Algorithms, Data Structures, and Problem Solving with C++_, chapter 20.
    Version:
    $Revision: 1.1 $ $Date: 2005/12/21 22:25:34 $
    Author:
    Nick Collier
    • Constructor Summary

      Constructors 
      Constructor Description
      PriorityQueue​(T minValue, Comparator<T> comp)
      Creates a PriorityQueue with a default initial size of 13.
      PriorityQueue​(T minValue, Comparator<T> comp, int size)
      Creates a PriorityQueue with the specified initial size.
    • Constructor Detail

      • PriorityQueue

        public PriorityQueue​(T minValue,
                             Comparator<T> comp)
        Creates a PriorityQueue with a default initial size of 13. The minValue param is expected to less than any value put in the queue.
        Parameters:
        minValue - the absolute minimum value put in the queue.
        comp - the comparator used to order the items in the queue.
      • PriorityQueue

        public PriorityQueue​(T minValue,
                             Comparator<T> comp,
                             int size)
        Creates a PriorityQueue with the specified initial size. The minValue param is expected to less than any value put in the queue.
        Parameters:
        minValue - the absolute minimum value put in the queue.
        comp - the comparator used to order the items in the queue.
        size - the intial size of the queue
    • Method Detail

      • insert

        public void insert​(T obj)
        Insert the specified item into the queue.
      • peekMin

        public T peekMin()
        Get the minimum element from the queque without removing it from the queue. If heap order is not currently correct, the heap will be fixed before the minimum is returned.
        Returns:
        the minimum element from the queque
      • popMin

        public T popMin()
        Remove the minimum element from the queque and return it. If heap order is not currently correct, the heap will be fixed before the minimum is returned.
        Returns:
        the minimum element from the queque
      • toss

        public void toss​(T obj)
        Insert the specified item into the queue without maintain heap order.
        Parameters:
        obj - the item to insert into the queue
      • clear

        public void clear()
        Removes all elements from the queue.
      • fixHeap

        public void fixHeap()
        Reinstate the heap order. This will fix the tree, ordering it correctly.
      • isEmpty

        public boolean isEmpty()
        Returns true if the queue is empty, otherwise false.
        Returns:
        true if the queue is empty, otherwise false.
      • size

        public int size()
        Gets the number of elements in the queue.
        Returns:
        the number of elements in the queue.