[Jayp806]

I have an assignment for my advanced data structures class where I'm supposed to take the teacher's Priority Queue class and modify it as so:

"Modify the PriorityQueue class we developed so that when there is more than a single item in the PriorityQueue with highest priority, the one that has been in the longest is the one removed. The underlying data structure must still be the array representation of the heap, but otherwise you are free to make changes as long as they do not change the interface itself."



Here is the source code.

public class PriorityQueue 
{
   private Comparable[] HeapArray;
   int     Last, Limit;

   public PriorityQueue(int Capacity)
   {
      HeapArray = new Comparable[Capacity+1];
      Last      = 0;
      Limit     = Capacity;
      return;
   }
   // end constructor

   public PriorityQueue()
   {
      HeapArray = new Comparable[101];
      Last      = 0;
      Limit     = 100;
      return;
   }
   // end constructor

   public void Insert(Comparable PQI)
   {
      if (Last == Limit)
      {
         System.out.println("Priority Queue Overflow!");
         System.exit(0);
      }
      // end if

      HeapArray[++Last] = PQI;
      this.UpHeap(Last);
      return;
   }
   // end public method Insert

   private void UpHeap(int k)
   {
      Comparable V;

      V = HeapArray[k];
   
      while (k > 1  &&  HeapArray[k/2].compareTo(V) < 0)
      {
         HeapArray[k] = HeapArray[k/2];
         k = k/2;
      }
      // end while

      HeapArray[k] = V;
      return;
   }
   // end private method UpHeap

   public Comparable Remove()
   {
      Comparable PQI ;

      if (Last == 0)
      {
         System.out.println("Priority Queue Underflow!");
         System.exit(0);
      }
      // end if

      PQI = HeapArray[1];
      HeapArray[1] = HeapArray[Last--];
      this.DownHeap(1);
      return PQI;
   }
   // end public method Remove

   private void DownHeap(int k)
   {
      Comparable V;
      int    j;

      V = HeapArray[k];
   
      while (k <= Last/2)
      {
         j = k+k;

         if (j < Last  &&  HeapArray[j].compareTo(HeapArray[j+1]) < 0)
            j++;
         // end if

         if (V.compareTo(HeapArray[j]) >= 0)
            break;
         // end if

         HeapArray[k] = HeapArray[j];
         k = j;
      }
      // end while

      HeapArray[k] = V;
      return;
   }
   // end private method DownHeap

   public boolean IsEmpty()
   {
      if (Last == 0)
         return true;
      else
         return false;
      // end if
   }
   // end public method IsEmpty

   public boolean IsFull()
   {
      if (Last == Limit)
         return true;
      else
         return false;
      // end if
   }
   // end public method IsFull

   public int Length()
   {
      return Last;
   }
   // end public method Length
}
// end class PriorityQueue

I've been told by former students of the class that a good idea would be to use an array as a time stamp to keep track of when something is inserted or removed from the Queue. I have no idea how to implement this.I'm thinking that modifying the upheap method is the way to do this. If you're able to put the item with highest priority and that has been in the longest at the front of the Queue, the remove function shouldn't have to be modified. Any help would be greatly appreciated.

[Dogstopper]

""Modify the PriorityQueue class we developed so that when there is more than a single item in the PriorityQueue with highest priority, the one that has been in the longest is the one removed""

MY understanding of this problem is that if there items with highest priority (say two with a priority of one), then you are to remove the oldest highest priority item. Does this not mean that only one item can be the "highest" priority, cause if you add any highests, it removes the last highest one. Think about that.

[Jayp806]

The instructor explicitly said that if there are two items in the Queue with the same priority, the one that was put in the Queue is removed firstht For example, if you have two items with a priority of 9 and 9 is the highest priority, when you call the Remove function the 9 that was put in the Queue first is taken out.I'm sorry if the instructions weren't specific enough.

This post has been edited by Jayp806: 24 September 2010 - 08:24 PM

[codyH]

As you are storing Comparables inside the PQ you could simply add a data member to your comparable object that has the time inserted into the PQ as its value, so then when two or more items of equal priority occur you default based on time.

[pbl]

The easiest way would be to have an array[][] of Comparable like [10][101]
[10] for priority 0 to 9

When inserting an element you put it in the array of its priority
When removing an element scan the 10 priority subarray for the first one with element(s) into it an retreive from that array the first oen put in