Create a new Java class in a file named "ListPQ.java" that implements the Queue interface and uses the LinkedList provided by the JCF to implement a priority queue. Note that LinkedList does not automatically order values based on priority, so it will be up to you to make sure that values are removed in priority order. You should try to implement your priority queue as efficiently as possible - basic operations should run in constant or linear time. Your priority queue need only work with integers. Do not modify any of the provided code. //This is ArrayHeap (provided code) import java.util.Arrays; public class ArrayHeap implements Heap { private int[ ] array; private int size; public ArrayHeap() { array = new int[3]; size = 0; } @Override public void add(int value) { // add pt 1 if(size == array.length) { array = Arrays.copyOf(array, size*2); } array[size] = value; // sifting up int child = size; int parent = (child - 1) / 2; while(array[parent] > array[child]) { swap(parent, child); child = parent; parent = (child - 1) / 2; } size++; // don't forget! } @Override public int remove() { // most of part 1 int temp = array[0]; size--; swap(0, size); array[size] = 0; // sifting down int parent = 0; while(parent < size) { int left = parent * 2 + 1; int right = left + 1; int dest = parent; if(left < size) { dest = left; } if(right < size && array[right] < array[left]) { dest = right; } if(array[dest] < array[parent]) { swap(dest, parent); parent = dest; } else { break; } } // last bit of part 1 return temp; } @Override public int size() { return size; } @Override public String toString() { return Arrays.toString(array) + ", " + size; } /** * Helper function that swaps the values at the two specified indexes if * the indexes are different. * * @param a The first index. * @param b The second index. */ private void swap(int a, int b) { if(a != b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; } } /** * Tests the class by making a heap, adding several values, and then * removing the values. * * @param args Command line arguments. Ignored. */ public static void main(String[] args) { Heap heap = new ArrayHeap(); System.out.println(heap); heap.add(5); heap.add(4); heap.add(3); heap.add(2); heap.add(1); System.out.println(heap); System.out.println(heap.remove() + ", " + heap); System.out.println(heap.remove() + ", " + heap); System.out.println(heap.remove() + ", " + heap); System.out.println(heap.remove() + ", " + heap); System.out.println(heap.remove() + ", " + heap); } } // This is the Heap (provided code) public interface Heap { /** * Adds a value to the heap. * * @param value The value to add. */ void add(int value); /** * Removes and returns the highest priority value currently in the heap. * * @return The highest priority value currently in the heap. Also removes * the value from the heap. */ int remove(); /** * Returns the number of values currently in the heap. * * @return The number of values currently in the heap. */ int size(); } // This is Queue (provided code) public interface Queue { /** * Adds a value to the back of the queue. * * @param value The value to add to the queue. */ void enqueue(E value); /** * Removes and returns the value at the front of the queue. * * @return The value at the front of the queue. */ E dequeue(); /** * Returns the number of elements currently stored in the queue. * * @return The number of elements currently stored in the queue. */ int size(); }
- Create a new Java class in a file named "ListPQ.java" that implements the Queue
interface and uses the LinkedList provided by the JCF to implement a priority queue.
Note that LinkedList does not automatically order values based on priority, so it will
be up to you to make sure that values are removed in priority order. You should try to
implement your priority queue as efficiently as possible - basic operations should run in
constant or linear time. Your priority queue need only work with integers. Do not modify
any of the provided code.
//This is ArrayHeap (provided code)
import java.util.Arrays;
public class ArrayHeap implements Heap {
private int[ ] array;
private int size;
public ArrayHeap() {
array = new int[3];
size = 0;
}
@Override
public void add(int value) {
// add pt 1
if(size == array.length) {
array = Arrays.copyOf(array, size*2);
}
array[size] = value;
// sifting up
int child = size;
int parent = (child - 1) / 2;
while(array[parent] > array[child]) {
swap(parent, child);
child = parent;
parent = (child - 1) / 2;
}
size++; // don't forget!
}
@Override
public int remove() {
// most of part 1
int temp = array[0];
size--;
swap(0, size);
array[size] = 0;
// sifting down
int parent = 0;
while(parent < size) {
int left = parent * 2 + 1;
int right = left + 1;
int dest = parent;
if(left < size) {
dest = left;
}
if(right < size && array[right] < array[left]) {
dest = right;
}
if(array[dest] < array[parent]) {
swap(dest, parent);
parent = dest;
} else {
break;
}
}
// last bit of part 1
return temp;
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
return Arrays.toString(array) + ", " + size;
}
/**
* Helper function that swaps the values at the two specified indexes if
* the indexes are different.
*
* @param a The first index.
* @param b The second index.
*/
private void swap(int a, int b) {
if(a != b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
/**
* Tests the class by making a heap, adding several values, and then
* removing the values.
*
* @param args Command line arguments. Ignored.
*/
public static void main(String[] args) {
Heap heap = new ArrayHeap();
System.out.println(heap);
heap.add(5);
heap.add(4);
heap.add(3);
heap.add(2);
heap.add(1);
System.out.println(heap);
System.out.println(heap.remove() + ", " + heap);
System.out.println(heap.remove() + ", " + heap);
System.out.println(heap.remove() + ", " + heap);
System.out.println(heap.remove() + ", " + heap);
System.out.println(heap.remove() + ", " + heap);
}
}
// This is the Heap (provided code)
public interface Heap {
/**
* Adds a value to the heap.
*
* @param value The value to add.
*/
void add(int value);
/**
* Removes and returns the highest priority value currently in the heap.
*
* @return The highest priority value currently in the heap. Also removes
* the value from the heap.
*/
int remove();
/**
* Returns the number of values currently in the heap.
*
* @return The number of values currently in the heap.
*/
int size();
}
// This is Queue (provided code)
public interface Queue {
/**
* Adds a value to the back of the queue.
*
* @param value The value to add to the queue.
*/
void enqueue(E value);
/**
* Removes and returns the value at the front of the queue.
*
* @return The value at the front of the queue.
*/
E dequeue();
/**
* Returns the number of elements currently stored in the queue.
*
* @return The number of elements currently stored in the queue.
*/
int size();
}
Step by step
Solved in 3 steps with 1 images
