Remove any initial package declaration that might be added to your file in * cas
ID: 3801932 • Letter: R
Question
Remove any initial package declaration that might be added to your file in * case you edit it in eclipse. * * The goal of the homework is to create two ArrayList based implementations of * a Priority Queue as explained in Section 9.2 (in 9.2.4 and 9.2.5) of the * textbook. * * These are to be made by completing the classes PQunsorted and PQsorted as * given below. In completing these classes you should only use the instance * members array, capacity and size, but you should add implementations for the * required Priority Queue methods. Only change their methods as indicated by * TODO instructions * * Finally, you should make the main program display your name and 8 digit ID * number. * * Your implementations should work interchangeably with the heap based version. * The main program runs both your implementations and the (correct) heap based * one from class at once. When your code is correct, it should produce any * output three times over. ********************************************************************/ class PQunsorted<K extends Comparable<K>> implements PriorityQueue<K> { K[] data; int size; int capacity; public PQunsorted() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; } // easy insertion public void insert(K x) throws Exception { if (size >= capacity) throw new Exception("Queue full"); data[size++] = x; } public K removeMin() throws Exception { // TODO complete code to remove min here return null; } } class PQsorted<K extends Comparable<K>> implements PriorityQueue<K> { K[] data; int size; int capacity; public PQsorted() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; } public void insert(K x) throws Exception { // TODO complete code to insert x, keeping the array sorted so the min is at the end } // easy removal in this implementation public K removeMin() throws Exception { if (size == 0) throw new Exception("Queue Empty"); return data[--size]; } } // ---------------------- main program to test implementations --- class D00000000 { public static void main(String args[]) { PriorityQueue<String> pq = new HeapPriorityQueue<>(); PriorityQueue<String> pqU = new PQunsorted<>(); PriorityQueue<String> pqS = new PQsorted<>(); boolean done = false; Scanner sc = new Scanner(System.in); while (!done) { try { // add your name into the following print statement System.out.println( " Program by: xxxx ---- cmds are + - Q: >>"); String cmd = sc.next(); String entry = null; char command = cmd.charAt(0); if (command == '+') entry = sc.next(); switch (cmd.charAt(0)) { case 'Q': done = true; break; case '+': pq.insert(entry); pqU.insert(entry); pqS.insert(entry); break; case '-': System.out.print(pq.removeMin() + " "); System.out.print(pqU.removeMin() + " "); System.out.print(pqS.removeMin() + " "); break; } } catch (Exception e) { System.out.println("Error " + e.toString()); } } sc.close(); } }
Explanation / Answer
Answer:
class PriorityQueueApp
{
vector<int> input;
void rightMove(int less, int large);
void leftMove(int less, int large);
void constructHeap();
public:
PriorityQueue(){}
PriorityQueue(vector<int>& elements)
{
input = elements;
constructHeap();
}
void enqueue(int value);
int dequeue();
void print();
};
void PriorityQueue::enqueue(int value)
{
input.push_back(value);
leftMove(0, input.size() - 1);
return;
}
int PriorityQueue::dequeue()
{
assert(input.size() != 0);
int last = input.size() - 1;
int read = input[0];
input[0] = input[last];
input[last] = read;
input.pop_back();
rightMove(0, last-1);
return read;
}
void PriorityQueue::print()
{
int size = input.size();
for (int i = 0; i < size; ++i)
cout << input[i] << " ";
cout << endl;
}
void PriorityQueue::leftMove(int less, int large)
{
int indexchild = large;
while (indexchild > less)
{
int indexparent = (indexchild-1)/2;
if (input[indexchild] > input[indexparent])
{
int read = input[indexchild];
input[indexchild] = input[indexparent];
input[indexparent] = read;
indexchild = indexparent;
}
else
{
break;
}
}
return;
}
void PriorityQueue::rightMove(int less, int large)
{
int number = less;
while ((number*2)+1 <= large)
{
int leftChild = (number * 2) + 1;
int rightChild = leftChild + 1;
int exchangeindex = number;
if (input[exchangeindex] < input[leftChild])
{
exchangeindex = leftChild;
}
if ((rightChild <= large) && (input[exchangeindex] < input[rightChild]))
{
exchangeindex = rightChild;
}
if (exchangeindex != number)
{
int read = input[number];
input[number] = input[exchangeindex];
input[exchangeindex] = read;
number = exchangeindex;
}
else
{
break;
}
}
return;
}
void PriorityQueue::constructHeap()
{
int size = input.size();
int betweenindex = (size -2)/2;
while (betweenindex >= 0)
{
rightMove(betweenindex, size-1);
--betweenindex;
}
return;
}