In this lab, you will develop an implementation of the PurePriorityQueue interface that is fair, that is, in which ties for highest-priority element will be resolved in favor of the element that has been on the priority queue for the longest time.

Program from Chapter 13

import java.io.*;
import java.util.*;

public class StudentPQ
{ 
  protected final String SENTINEL = "***";
 
  protected final String PROMPT = "In the Input line, please enter " +
    "a student's name and GPA. To quit, enter " + SENTINEL;
    
  PurePriorityQueue<Student> pq;
  
  
  /**
   * The StudentPQ has been initialized.
   **/
  public StudentPQ() 
  {  
    //        pq = new Heap<Student>();
    pq = new FairHeap<Student>();
  } // default constructor
  
  /**
   * The Student read into line has been processed.
   **/
  public void getStudents() 
  {    
    final String RESULTS = "\nHere are the student names and GPAs:";
    
    String line = new String();
    
    BufferedReader reader = new BufferedReader(new InputStreamReader 
                                                 (System.in));
    
    while (true)
    {
      try
      {
        System.out.print (PROMPT);  
        line = reader.readLine();
        if (line.equals (SENTINEL)) 
          break;     
        pq.add (new Student (line));
      }//try
      catch (IOException e)
      {
        System.out.println (e);
      }//catch IOException
      catch (NoSuchElementException e)
      {
        System.out.println (e);
      } // catch NoSuchElementException
      catch (NumberFormatException e)
      {
        System.out.println (e);
      } // catch NumberFormatException
    }//while
    System.out.println (RESULTS);
    while (!pq.isEmpty())
      System.out.println (pq.removeMin());
  } // method getStudents
  
} // class StudentPQ

The Student class is as follows:

import java.util.*;

public class Student implements Comparable 
{
  protected String name;
  
  protected double GPA;
  
  
  /**
   * This Student has been initialized from s.
   * 
   * @param s a String entered.
   **/
  public Student (String s) 
  {
    StringTokenizer tokens = new StringTokenizer (s);
    
    name = tokens.nextToken();
    GPA = Double.parseDouble (tokens.nextToken());    
  } // constructor
  

  /**
   * An int <, == or > 0 has been returned depending on whether this
   * Student's GPA is less than, equal to or greater than o1's GPA.
   * 
   * @param o1 an Object to be compared to the calling object.
   * 
   * @return an int which indicates whether the calling object is
   *         greater or less than, or equal to o1.
   **/
  public int compareTo (Object o1) 
  {
    
    if (GPA < ((Student)o1).GPA)
      return -1;
    if (GPA ==((Student)o1).GPA)
      return 0;
    return 1;    
  } // method compareTo
  
  
  /**
   * A string representing the student is returned.
   * 
   * @return a String which represents the Student.
   **/
  public String toString() 
  {   
    return name + "  " + GPA;    
  } // method toString
  
} // class Student

For input of:

Soumya 3.4
Navdeep 3.5
Viet 3.5

the output is:

Soumya 3.4
Viet 3.5
Navdeep 3.5

The unfairness here is that Navdeep is added to pq earlier than Viet, but Viet is output before Navdeep, even though they have the same GPA. To see why this happens, we need to look at the heap used to hold the priority queue. After the three insertions, we have:

Here, for your convenience, is the percolateUp() method from Heap.java:

/**
 *  Restores the heap properties to this Heap object, which was a 
 *  heap except, possibly, at index size() - 1.
 *  The worstTime(n) is O(log n), and averageTime(n) is constant.
 *
 */
protected void percolateUp()
{
      int child = list.size() - 1,
          parent;

      while (child > 0)
      {
          parent = (child - 1) >> 1;  // >>1 is slightly faster than / 2
          if (compare (list.get (child), list.get (parent)) >= 0)
                break;
          swap (parent, child);
          child = parent;
      } // while
} // method percolateUp

When pq.removeMin() is called, pq's last element -- Viet 3.5 
-- is stored at index 0, size is decremented to 1, and 
percolateDown (0) is called.  Just before that call to 
percolateDown, the heap contains:

  


Here, for your convenience, is the percolateDown method:


/** 
 *  Restores the heap properties to this Heap object, which is a heap except,
 *  possibly, at a specified position.
 *  The worstTime(n) is O(log n).
 *
 *  @param start - the specified position where the restoration of the heap 
 *                 will begin.
 *
*/                     	
protected void percolateDown (int start)
{
     int parent = start,
         child = (parent << 1) + 1;

     while (child < list.size())
     {
         if (child < list.size() -1 &&
                         compare (list.get (child), list.get (child+1)) > 0)
             child++; // child indexes smallest child
         if (compare (list.get (child), list.get (parent)) >= 0)
             break;
         swap (parent, child);
         parent = child;
         child = (parent << 1) + 1;
     } // while
} // method percolateDown


Because the condition


compare (list.get (child), list.get (parent)) >= 0


is true, the loop is exitted.  During the next call to 
pq.removeMin(), list.get (0) -- Viet 3.5 -- is printed.