Question

Chapter 4 programing project 4.4 The priority queue shown in Listing 4.6 features fast removal of the high-priority item but slow insertion of new items. Write a program with a revised PriorityQ class that has fast O(1) insertion time but slower removal of the high priority item.
Please submit one MS WOrd file with java code and screenshots showing your testing.

Answer 1

PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

class PriorityQ {
  private int maxSize;

  private long[] queArray;

  private int nItems;

  public PriorityQ(int s) { // constructor
    maxSize = s;

    queArray = new long[maxSize];

    nItems = 0;
  }

  public void insert(long item) {
    if (nItems < queArray.length) {
      queArray[nItems] = item;

      nItems++;
    }
  }

  public long remove() {
    int indexMin = 0;

    for (int i = 1; i < nItems; i++) {
      if (queArray[i] < queArray[indexMin]) {
        indexMin = i;
      }
    }

    long elem = queArray[indexMin];

    for (int i = indexMin; i < nItems - 1; i++) {
      queArray[i] = queArray[i + 1];
    }

    nItems--;

    return elem;
  }

  public long peekMin() {
    int indexMin = 0;

    for (int i = 1; i < nItems; i++) {
      if (queArray[i] < queArray[indexMin]) {
        indexMin = i;
      }
    }

    return queArray[indexMin];
  }

  public boolean isEmpty() {
    return (nItems == 0);
  }

  public boolean isFull() {
    return (nItems == maxSize);
  }

  public void display() {
    System.out.print("Queue contents: ");
    for (int i = 0; i < nItems; i++) {
      System.out.print(queArray[i]);

      if (i != nItems - 1) {
        System.out.print(", ");
      }
    }

    System.out.println();
  }
}

class PriorityQApp {

  public static void main(String[] args) {
    PriorityQ thePQ = new PriorityQ(5);

    thePQ.insert(30);

    thePQ.insert(50);

    thePQ.insert(10);

    thePQ.insert(40);

    thePQ.insert(20);

    //displaying the queue

    thePQ.display();

    while (!thePQ.isEmpty()) {
      long item = thePQ.remove();

      //displaying the removed element

      System.out.println(item + " is removed");

      //displaying current queue contents

      thePQ.display();
    } // end while
  } // end main()
  // -------------------------------------------------------------

} // end class PriorityQApp