3.Provide a generic Java class named SortedPriorityQueue that implements a prior
ID: 3743415 • Letter: 3
Question
3.Provide a generic Java class named SortedPriorityQueue that implements a priority queue using a sorted list implemented with the Java ArrayList class. Make the implementation as efficient as possible.
4. Consider the following sorting algorithm that uses the class you wrote in the previous problem:
void sort(int[] array)
{
SortedPriorityQueue<Integer> queue = new SortedPriorityQueue();
for (int i = 0; i < array.length; i++)
queue.add(array[i]);
for (int i = 0; i < array.length; i++)
array[i] = queue.remove();
}
Analyze its execution time efficiency in the worst case. In your analysis you may ignore the possibility that the array list may overflow and need to be copied to a larger array. Indicate whether this implementation is more or less efficient than the one that uses the Java priority queue.
***Please don't copy previous written answers and separate answer 3 from answer 4**********
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// SortedPriorityQueue.java
import java.util.ArrayList;
public class SortedPriorityQueue<T extends Comparable<T>> {
// array list to represent elements as PriorityQueue
ArrayList<T> queue;
// default constructor
public SortedPriorityQueue() {
// initializing queue
queue = new ArrayList<T>();
}
/**
* method to add an element to the queue
*
* @param item
* item to be added (must be comparable)
*/
public void add(T item) {
if (queue.isEmpty()) {
/**
* Queue is empty Adding as the first element
*/
queue.add(item);
} else {
if (item.compareTo(queue.get(0)) < 0) {
/**
* Adding before current first object
*/
queue.add(0, item);
} else {
// a flag to denote if the object is added or not
boolean added = false;
// looping through all objects
for (int i = 0; i < queue.size() - 1; i++) {
/**
* checking if the object can be added to the middle of
* current pair of elements (between positions i and i+1)
*/
if (item.compareTo(queue.get(i)) >= 0
&& item.compareTo(queue.get(i + 1)) < 0) {
queue.add(i + 1, item);
// added to the middle
added = true;
break;
}
}
// finally, if not added, adding to end
if (!added) {
queue.add(item);
}
}
}
}
/**
* method to remove an element from the queue This method will always run in
* O(1) time efficiency
*
* @return the element at first position (lowest in sorted elements)
*/
public T remove() {
// removing and returning the first element if the queue is not empty
if (!queue.isEmpty()) {
return queue.remove(0);
}
return null;
}
//returns true if queue is empty
public boolean isEmpty() {
return queue.isEmpty();
}
@Override
public String toString() {
return queue.toString();
}
}
// Test.java
import java.util.Arrays;
import java.util.PriorityQueue;
public class Test {
static void sort(int[] array) {
SortedPriorityQueue<Integer> queue = new SortedPriorityQueue();
for (int i = 0; i < array.length; i++)
queue.add(array[i]);
for (int i = 0; i < array.length; i++)
array[i] = queue.remove();
}
/**
* method to compare SortedPriorityQueue with java built-in PriorityQueue
*/
static void testTimeEfficiency() {
/**
* creating instances of SortedPriorityQueue and java PriorityQueue
*/
PriorityQueue<Integer> javaQueue = new PriorityQueue<Integer>();
SortedPriorityQueue<Integer> customQueue = new SortedPriorityQueue<Integer>();
int numElements = 10000; // number of elements to be tested
long start, end;
double seconds;
//using an array of random numbers to add to both queues
int array[]=new int[numElements];
for (int i = 0; i < array.length; i++) {
//populating with random numbers under 100
array[i] = (int) (Math.random() * 100);
}
// recording start time
start = System.currentTimeMillis();
// adding elements to java PriorityQueue
for (int i = 0; i < numElements; i++) {
javaQueue.add(array[i]);
}
// recording end time
end = System.currentTimeMillis();
// finding time taken
seconds = (end - start) / 1000.0;
System.out.println("It took " + seconds + " seconds to add "
+ numElements + " elements to Java built in PriorityQueue");
/**
* performing similar test in SortedPriorityQueue
*/
start = System.currentTimeMillis();
for (int i = 0; i < numElements; i++) {
customQueue.add(array[i]);
}
end = System.currentTimeMillis();
seconds = (end - start) / 1000.0;
System.out.println("It took " + seconds + " seconds to add "
+ numElements + " elements to SortedPriorityQueue");
/**
* now testing removal time
*/
start = System.currentTimeMillis();
while (!javaQueue.isEmpty()) {
javaQueue.remove();
}
end = System.currentTimeMillis();
seconds = (end - start) / 1000.0;
System.out.println("It took " + seconds + " seconds to remove "
+ numElements + " elements from Java built in PriorityQueue");
start = System.currentTimeMillis();
while (!customQueue.isEmpty()) {
customQueue.remove();
}
end = System.currentTimeMillis();
seconds = (end - start) / 1000.0;
System.out.println("It took " + seconds + " seconds to remove "
+ numElements + " elements from SortedPriorityQueue");
}
public static void main(String[] args) {
/**
* creating an array
*/
int array[] = new int[50];
/**
* Adding 50 random elements
*/
for (int i = 0; i < array.length; i++) {
array[i] = (int) (Math.random() * 100);
}
System.out.println("Before sorting: " + Arrays.toString(array));
//sorting using SortedPriorityQueue
sort(array);
System.out.println("After sorting: " + Arrays.toString(array));
System.out
.println("Comparing SortedPriorityQueue with Java built in PriorityQueue");
//testing time efficiency
testTimeEfficiency();
}
}
/*OUTPUT*/
Before sorting:
[54, 30, 7, 6, 63, 71, 88, 36, 10, 75, 19, 0, 83, 53, 84, 87, 2, 56, 5, 59, 22, 8, 88, 60, 40, 48, 43, 47, 2, 51, 70, 72, 49, 7, 37, 78, 15, 73, 51, 34, 45, 44, 70, 23, 8, 70, 3, 52, 75, 84]
After sorting:
[0, 2, 2, 3, 5, 6, 7, 7, 8, 8, 10, 15, 19, 22, 23, 30, 34, 36, 37, 40, 43, 44, 45, 47, 48, 49, 51, 51, 52, 53, 54, 56, 59, 60, 63, 70, 70, 70, 71, 72, 73, 75, 75, 78, 83, 84, 84, 87, 88, 88]
Comparing SortedPriorityQueue with Java built in PriorityQueue
It took 0.024 seconds to add 10000 elements to Java built in PriorityQueue
It took 0.144 seconds to add 10000 elements to SortedPriorityQueue
It took 0.033 seconds to remove 10000 elements from Java built in PriorityQueue
It took 0.027 seconds to remove 10000 elements from SortedPriorityQueue
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.