import java.io.*;
import java.lang.*;

public class PriorityQueueSorting {

   public static void main(String [] ar) {
 
      // create an array of Strings to sort
         String[] someNames = {"Ken", "Pam", "Meg", "Jan",  "Ned",
                               "Peg", "Deb", "Jim",  "Amy", "Tom"};
     
      // store the names as PQItems in an array A of ComparisonKeys
      // and print them
      int n = someNames.length;
      ComparisonKey[] A = new ComparisonKey[n];
      for (int i = 0;  i < n;  i++) {
         A[i] = new PQItem(someNames[i]);
         System.out.print(A[i] + ", ");
      }                            // the unsorted names printed are those
      System.out.println();                        // shown on lines 11:12
     
      // sort the array A using priorityQueueSorting
      priorityQueueSort(A);
       
      // print the values in the array A after sorting
      for (int i = 0; i < n; i++) {
         System.out.print(A[i] + ", ");
      }                                   // the sorted names printed are:
      System.out.println();                    // Amy, Deb, Jan, Jim, Ken,
                                               // Meg, Ned, Pam, Peg, Tom.
   } // end init()

/* ---------------*/

   static void priorityQueueSort(ComparisonKey[] A) {
       
      int i;                             // let i be an array index variable
      int n = A.length;         // n is the length of the array to be sorted
       
      PriorityQueue PQ = new PriorityQueue();          // let PQ be an empty
                                                           // priority queue
      for (i = 0; i < n; i++) PQ.insert(A[i]);   // insert A's items into PQ
    
      for (i = n-1; i >= 0; i--) A[i] = PQ.remove();  // put PQ's items into
                                                 // A in reverse index order
   }
     
} // end class PriorityQueueApplet