Class PriorityQueue


  • public class PriorityQueue
    extends java.lang.Object
    A priority queue over a set of Comparable objects.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.ArrayList items  
      private int size  
    • Constructor Summary

      Constructors 
      Constructor Description
      PriorityQueue()
      Creates a new empty priority queue
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(java.lang.Comparable x)
      Insert into the priority queue.
      void clear()
      Make the priority queue logically empty.
      boolean isEmpty()
      Test if the priority queue is logically empty.
      java.lang.Object poll()
      Remove the smallest item from the priority queue.
      private void reorder​(int hole)
      Internal method to percolate down in the heap.
      int size()
      Returns size.
      • Methods inherited from class java.lang.Object

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

      • size

        private int size
      • items

        private java.util.ArrayList items
    • Constructor Detail

      • PriorityQueue

        public PriorityQueue()
        Creates a new empty priority queue
    • Method Detail

      • add

        public void add​(java.lang.Comparable x)
        Insert into the priority queue. Duplicates are allowed.
        Parameters:
        x - the item to insert.
      • isEmpty

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

        public int size()
        Returns size.
        Returns:
        current size.
      • clear

        public void clear()
        Make the priority queue logically empty.
      • poll

        public java.lang.Object poll()
        Remove the smallest item from the priority queue.
        Returns:
        the smallest item, or null if empty
      • reorder

        private void reorder​(int hole)
        Internal method to percolate down in the heap.
        Parameters:
        hole - the index at which the percolate begins.