Will rate life saver For this assignment, you will write four implementations of
ID: 3630578 • Letter: W
Question
Will rate life saver
For this assignment, you will write four implementations of a Priority Queue. For this ADT, removal operations always return the object in the queue of highest priority that has been in the queue the longest. That is, no object of a given priority is ever removed as long as the queue contains one or more object of a higher priority. Within a given priority FIFO order must be preserved. By convention, when two items with different priorites are compared, the item with higher priority is less than the item with lower priority. Thus, a remove operation on a priority queue that contains two objects with different priorities, will always return the smallest item in the queue.
Your four implementations will be:
All four implementations must have identical behavior, and must implement the PriorityQueue interface (provided). The array-based implementations must have two constructors, a default constructor with no arguments that uses the DEFAULT_MAX_CAPACITY constant from the PriorityQueue.java interface, and a constructor that takes a single integer parameter that represents the maximum capacity of the PQ. [ NOTE: Do not declare the DEFAULT_MAX_CAPACITY variable in your classes. The variable in the interface is inherited. ]
The PriorityQueue interface follows:
Thus, your project will consist of the following files. You must use exactly these filenames.
Explanation / Answer
public class OrderedArrayMaxPQ<Key extends Comparable<Key>> {
private Key[] pq; // elements
private int N; // number of elements
// set inititial size of heap to hold size elements
public OrderedArrayMaxPQ(int capacity) {
pq = (Key[]) (new Comparable[capacity]);
N = 0;
}
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
public Key delMax() { return pq[--N]; }
public void insert(Key key) {
int i = N-1;
while (i >= 0 && less(key, pq[i])) {
pq[i+1] = pq[i];
i--;
}
pq[i+1] = key;
N++;
}
private boolean less(Key v, Key w) {
return (v.compareTo(w) < 0);
}
private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
public static void main(String[] args) {
OrderedArrayMaxPQ<String> pq = new OrderedArrayMaxPQ<String>(10);
pq.insert("this");
pq.insert("is");
pq.insert("a");
pq.insert("test");
while (!pq.isEmpty())
StdOut.println(pq.delMax());
}
}
public class UnorderedArrayMaxPQ<Key extends Comparable<Key>> {
private Key[] pq; // elements
private int N; // number of elements
// set inititial size of heap to hold size elements
public UnorderedArrayMaxPQ(int capacity) {
pq = (Key[]) new Comparable[capacity];
N = 0;
}
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
public void insert(Key x) { pq[N++] = x; }
public Key delMax() {
int max = 0;
for (int i = 1; i < N; i++)
if (less(max, i)) max = i;
exch(max, N-1);
return pq[--N];
}
private boolean less(int i, int j) {
return (pq[i].compareTo(pq[j]) < 0);
}
private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
public static void main(String[] args) {
UnorderedArrayMaxPQ<String> pq = new UnorderedArrayMaxPQ<String>(10);
pq.insert("this");
pq.insert("is");
pq.insert("a");
pq.insert("test");
while (!pq.isEmpty())
StdOut.println(pq.delMax());
}
}
UNORDERED LINKED LIST
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.