Data Structures, Algorithms, & Applications in Java
Chapter 13, Exercise 1

We use ArrayLinearListWithIterator as the base class. The code is given below. Since we do not access the data members of ArrayLinearListWithIterator, the same code can be used to derive from Vector or ArrayList instead.

A test program and output appear in the files MaxPriorityQueueFromArrayList.*.

The complexity of put is Theta(1), because the new element is inserted at the right end of the linear list. The complexity of removeMax and getMax is

O(n), because all elements in the list
are examined.

public class MaxPriorityQueueFromArrayList
                        extends ArrayLinearListWithIterator
                        implements MaxPriorityQueue
{
   // constructors
   /** create a priority queue with the given initial capacity */
   public MaxPriorityQueueFromArrayList(int initialCapacity)
      {super(initialCapacity);}
   
   /** create a priority queue with initial capacity 10 */
   public MaxPriorityQueueFromArrayList()
      {super(10);}

   // methods isEmpty and size are inherited

   /** return maximum element
     * return null if the priority queue is empty */
   public Comparable getMax()
   {
      if (size() == 0)
         // priority queue is empty
         return null;
   
      // find max element by examining all elements in the queue
      // use the iterator it to avoid accessing the
      // data members element and size
      Iterator it = iterator();
      Comparable currentMax = (Comparable) get(0);
      it.next();
      while (it.hasNext())
      {
         Object temp = it.next();
         if (currentMax.compareTo(temp) < 0)
            currentMax = (Comparable) temp;
      }

      return currentMax;
   }

   /** put theElement into the priority queue */
   public void put(Comparable theElement)
      {add(size(), theElement);}
   
   /** remove max element and return it */
   public Comparable removeMax()
   {
      // if priority queue is empty return null
      if (size() == 0)
         return null;
   
      // find max element by examining all elements in the queue
      Iterator it = iterator();
      Comparable currentMax = (Comparable) get(0);
      int pos = 0;             // index of currentMax
      it.next();
      int currentPos = 0;      // index of current element
      while (it.hasNext())
      {
         Object temp = it.next();
         currentPos++;
         if (currentMax.compareTo(temp) < 0)
         {
            currentMax = (Comparable) temp;
            pos = currentPos;
         }
      }

      // remove max element from priority queue
      remove(pos);
   
      return currentMax;
   }
}

Data Structures, Algorithms, & Applications in Java Chapter 13, Exercise 1

Data Structures, Algorithms, & Applications in Java
Chapter 13, Exercise 1