Class PriorityQueue<E extends java.lang.Comparable<E>>

  • Type Parameters:
    E - the type of comparable elements held in this queue

    public class PriorityQueue<E extends java.lang.Comparable<E>>
    extends java.lang.Object
    An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering. A priority queue does not permit null elements.

    The queue can be set to accept or reject the insertion of non unique elements through the method setUniqueness. Uniqueness is disabled by default.

    The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value (provided that uniqueness is set to false), the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

    A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically.

    Iterating the queue with the method get is not guaranteed to traverse the elements of the priority queue in any particular order.

    Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (add and poll ; and constant time for the retrieval methods (peek and size).

    • Constructor Summary

      Constructors 
      Constructor Description
      PriorityQueue()
      Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
      PriorityQueue​(int initialCapacity)
      Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E e)
      Inserts the specified element into this priority queue.
      void clear()
      Removes all of the elements from this priority queue.
      E get​(int index)
      Retrieves the element at the specified index.
      boolean getUniqueness()
      Returns a value indicating whether only unique elements are allowed to be inserted.
      E peek()
      Retrieves, but does not remove, the head of this queue.
      E poll()
      Retrieves and removes the head of this queue, or returns null if this queue is empty.
      void setUniqueness​(boolean uniqueness)
      Sets a flag indicating whether only unique elements are allowed to be inserted.
      int size()
      Returns the number of elements in this queue.
      • Methods inherited from class java.lang.Object

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

      • PriorityQueue

        public PriorityQueue()
        Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
      • PriorityQueue

        public PriorityQueue​(int initialCapacity)
        Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
        Parameters:
        initialCapacity - the initial capacity for this priority queue
    • Method Detail

      • getUniqueness

        public boolean getUniqueness()
        Returns a value indicating whether only unique elements are allowed to be inserted.
      • setUniqueness

        public void setUniqueness​(boolean uniqueness)
        Sets a flag indicating whether only unique elements are allowed to be inserted.
      • add

        public boolean add​(E e)
        Inserts the specified element into this priority queue. If uniqueness is enabled and this priority queue already contains the element, the call leaves the queue unchanged and returns false.
        Returns:
        true if the element was added to this queue, else false
        Throws:
        java.lang.ClassCastException - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering
        java.lang.NullPointerException - if the specified element is null
      • peek

        public E peek()
        Retrieves, but does not remove, the head of this queue. If this queue is empty null is returned.
        Returns:
        the head of this queue
      • get

        public E get​(int index)
        Retrieves the element at the specified index. If such an element doesn't exist null is returned.

        Iterating the queue by index is not guaranteed to traverse the elements in any particular order.

        Returns:
        the element at the specified index in this queue.
      • size

        public int size()
        Returns the number of elements in this queue.
      • clear

        public void clear()
        Removes all of the elements from this priority queue. The queue will be empty after this call returns.
      • poll

        public E poll()
        Retrieves and removes the head of this queue, or returns null if this queue is empty.
        Returns:
        the head of this queue, or null if this queue is empty.