Question

Comparing the insertion and removing performance between ALPQueue with HeapPQueue. Requirements:

1/ Task1: implement a concrete ALPQueue class (an ArrayList based priority queue) that extends the AbstractPQueue discussed in the class, along with PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class (any other implementation of above classes that are not compatible with List interface and AbstractPQueue class will not receive any credit).

2/ Task2: implement a concrete HeapPQueue class (a Heap based priority queue) that extends the AbstractPQueue discussed in the class. Similary, you also need PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class. The ADT of HeapPQueue class is given below:

public class HeapPQueue extends AbstractPQueue {
  private ArrayList list = new ArrayList();

  //constructor: your implementation

  public int size();
  public boolean isEmpty();
  public void heapUp(int i);
  public void heapDown(int i);
  public PQEntry insert(Integer key, String value);
  public PQEntry removeMin();
  public PQEntry min();
}

3/ Task3: write a performance test program to measure the performance of the above two classes in running time. To do that, you may want to construct two big priority queue instances: one for ALPQueue and one for HeapPQueue. Perform at least 5,000 (random numbers) insert() operations and 5,000 removeMin() operation for each priority queue. The procedure of your test program should be the following:

1. construct an instance of ALPQueue with the capacity of 5,000 entries;

2. construct an instance of HeapPQueue with the capacity of 5,000 entries;

3. construct an integer array with the capacity of 5,000 integers, then fill the array with 5,000 random integers (as the potential key values);

3. record the system time Ta_insert_before;

4. insert 5,000 data items into the ALPQueue instance (the keys are coming from the integer array, and their correponding values can be a String, e.g., CIS + key_value;

5. record the system time Ta_insert_after;

6. compute the insertion time consumption of the ALPQueue;

7. repeat steps 3-6 to remove 5,000 entries, and compute the removal time consumption;

8. repeat 3-7 for the instance of HeapPQueue;

9. print out the results

Your test program should print out the following information:

ALPQueue:

insert 5000 entries: xxx ms

remove 5000 entries: xxx ms

HeapPQueue:

insert 5000 entries: xxx ms

remove 5000 entries: xxx ms

Find below java classes provided by the instructor in class that go along with the assignment:

a) PQueue.java class:

public interface PQueue {
int size();
boolean isEmpty();
PQEntry min();
PQEntry removeMin();
PQEntry insert (Integer k, String v);
}
b) PQEntry.java class:

public class PQEntry {
   private Integer key;

   private String value;

   public PQEntry(Integer k, String v) {

   key = k;

   value = v;
   }
public PQEntry() {
   this(-1, null);
}
public Integer getKey() {

return key;
}
public String getValue() {

return value;
}
public void setKey(Integer k) {
key = k;
}
public void setValue(String v) {
value = v;
}
}

c) EntryComparator.java class:

import java.util.Comparator;
public class EntryComparator implements Comparator {
   public int compare(Object a, Object b) {

   int akey = ((PQEntry)a).getKey();

   int bkey = ((PQEntry)b).getKey();

   return akey - bkey;
   }
}

d) AbstractPQueue.java class:

public abstract class AbstractPQueue implements PQueue {
   private EntryComparator comp;

   protected AbstractPQueue() {

   this(new EntryComparator());

   }

   protected AbstractPQueue(EntryComparator c) {comp = c;}

   protected int compare (PQEntry a, PQEntry b) {

   return comp.compare(a,b);
   }
   public boolean isEmpty(){return size() == 0;}

}

e) ALPQueue.java class:

public class ALPQueue extends AbstractPQueue {
   private List list = new ArrayList();

   public ALPQueue() {super();}

   public ALPQueue (EntryComparator com) { super(com);}

   public int size() { return list.size();}
   public PQEntry insert (Integer k, String v) {
       PQEntry newest = new PQEntry (k,v);
   try {
       list.add(list.size(), newest);}

   catch (OutOfRangeException e) {

   System.out.println("Out of Range");
   }
   return newest;
   }
   private int findMin() {

       int min = 0;

       if(list.size() == 1) return min;

       try {

       for(int i = 1; i < list.size(); i++) {

       if(compare((PQEntry) list.get(min), (PQEntry) list.get(i)) > 0)

       min = i;
       }
       }
       catch (OutOfRangeException ex) {

       System.out.println("Out of Range");
       }
       return min;

       }
       public PQEntry min() {

           if(isEmpty()) {return null;}

           PQEntry en = null;

           try {

           en = (PQEntry) list.get(findMin());

           } catch (OutOfRangeException e) {

           System.out.println("Out of Range");

           } return en;

           }

           public PQEntry removeMin() {

           if(isEmpty()) {return null;}

           PQEntry en = null;

           try {

           en = (PQEntry) list.remove(findMin());}
           catch (OutOfRangeException e) {

           System.out.println("Out of Range");

           } return en;

}

}

f) List.java class:

public interface List {
   public int size();

   public boolean isEmpty();

   public Object get(int i) throws OutOfRangeException;

   public void set(int i, Object e) throws OutOfRangeException;

   public void add(int i, Object e) throws OutOfRangeException;

   public Object remove(int i) throws OutOfRangeException;

   }

g) OutOfRangeException.java class:

public class OutOfRangeException extends Exception {
   public OutOfRangeException(String str){
       System.out.println("OutOfRangeException:" + str);}
       public OutOfRangeException (){
       this("Out Of Range");}
  
}

h) ArrayList.java class:

public class ArrayList implements List {
   private int CAP;
   private int size;
   private Object[] item;
   public ArrayList(int capacity){
       this.size = 0;
       this.CAP = capacity;
       this.item = new Object [capacity];
   }
   public ArrayList () {
       this(100);
   }
   public int size(){
       return size;
       }
       public boolean isEmpty(){
       return size==0;
       }
       public Object get(int i) throws OutOfRangeException {
       if (i<0 || i>=size)
           throw new OutOfRangeException ("Out of Range");
       return item [i];
       }
       public void set(int i, Object e) throws OutOfRangeException {
           if (i<0 || i>=size)
               throw new OutOfRangeException ("Out of Range");
           item [i] = e;
       }
       public void add(int i, Object e) throws OutOfRangeException {
           if (i<0 || i>size)
               throw new OutOfRangeException ("Out of Range");
           for (int j = size - 1; j>=i; j--)
               item[j+1] = item [j];
           size++;
       }
       public Object remove(int i) throws OutOfRangeException {
           if (i<0 || i>=size)
               throw new OutOfRangeException ("Out of Range");
           Object answer = item[i];
           for (int j=i; j<size-1; j++)
               item[j] = item[j+1];
           item[size-1] = null;
           size--;
           return answer;
       }
}
Hope it's clear now!

Answer 1

// Java progrm to demonstrate working of priority queue in Java
import java.util.*;

class Example
{
   public static void main(String args[])
   {
       // Creating empty priority queue
       PriorityQueue<String> prioirty_queue =
                       new PriorityQueue<String>();

       // Adding items to the prioirty_queue using add()
       prioirty_queue.add("C");
       prioirty_queue.add("C++");
       prioirty_queue.add("Java");
       prioirty_queue.add("Python");

       // Printing the most priority element
       System.out.println("Head value using peek function:"
                                       + prioirty_queue.peek());
  
System.out.println("For Array Queue Execution Time:");
//divide by 1000000 to get milliseconds.
System.out.print("Time for 5000 insertions ::");
long startTime = System.nanoTime();
  
  
       for (int i = 1;i<5000 ; i++)
       prioirty_queue.add("Python");
      
   long endTime = System.nanoTime();
   long duration = (endTime - startTime);
   System.out.println(duration);
     
   System.out.print("\nTime for 5000 Deletions ::");
   long startTime1 = System.nanoTime();      
   for (int i = 1;i<5000 ; i++)
       prioirty_queue.poll();
long endTime1 = System.nanoTime();
long duration1 = (endTime1 - startTime1);
   System.out.println(duration1);
           // Removing the top priority element (or head) and
       // printing the modified prioirty_queue using poll()
  

   }
}

/**
* Created with IntelliJ IDEA.
* Implement a priority queue using a heap
* The heap is implemented using an array indexed from 1
*/
public class Heap_priority_Queue<T extends Comparable<T>> {
T[] arr;
int N;

public static void main(String[] args) {
Heap_priority_Queue<Integer> pq = new Heap_priority_Queue<Integer>();

System.out.println("For Heap Queue Execution Time:");
//divide by 1000000 to get milliseconds.
System.out.print("Time for 5000 insertions ::");
long startTime = System.nanoTime();
       for (int i = 1;i<5000 ; i++)
       pq.insert(i);
   long endTime = System.nanoTime();
   long duration = (endTime - startTime);
   System.out.println(duration);
     
     
   System.out.print("\nTime for 5000 Deletions ::");
   long startTime1 = System.nanoTime();
   for (int i = 1;i<5000 ; i++)
       pq.delMax();   
long endTime1 = System.nanoTime();
long duration1 = (endTime1 - startTime1);
   System.out.println(duration1);
  
}

public Heap_priority_Queue(){
arr = (T[]) new Comparable[2];
N = 0;
}

public void insert(T t){
if (N == arr.length - 1) resize(2*N + 1);
arr[++N] = t;
swim(N);
}

public T delMax(){
if (isEmpty()) return null;
T t= arr[1];
exchanger(1,N--);
arr[N+1] = null;
sink(1);

//resize this array
if (N == (arr.length -1)/4) resize((arr.length-1) / 2 + 1);
return t;
}
//helper methods
public String toString(){
StringBuffer sb = new StringBuffer();
for(int i = 1; i <= N; i ++)
sb.append(arr[i].toString()+" ");
return sb.toString();
}

private boolean isEmpty(){
return N == 0;
}
private void resize(int capacity){
T[] copy = (T[]) new Comparable[capacity];
for(int i = 1; i <= N; i ++ )
copy[i] = arr[i];
arr = copy;
}

private void swim(int k){
while(k > 1 && _least(k/2, k)){
exchanger(k/2,k);
k = k/2;
}
}

private void sink(int k){
while (2*k < N){
int j = 2 * k;
if(j < N && _least(j, j +1)) j = j + 1;
if(_least(j, k)) break;
exchanger(k,j);
k = j;
}
}

private boolean _least(int i, int j){
if (arr[i].compareTo(arr[j]) < 0)
return true;
return false;
}

private void exchanger(int i, int j){
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

COMMENT DOWN FOR ANY QUERIES,

AND LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.