Need help with a Java problem: -------------------------------------------------
ID: 3846399 • Letter: N
Question
Need help with a Java problem:
-----------------------------------------------------------------------------------------------------------------------------------------------------------
MinPQ.java:
import stdlib.*;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MinPQ<K extends Comparable<? super K>> implements Iterable<K> {
private K[] pq; // store items at indices 1 to N
private int N; // number of items on priority queue
private Comparator<? super K> comparator; // optional comparator
// helper function to double the size of the heap array
@SuppressWarnings("unchecked")
private void resize(int capacity) {
if (capacity <= N) throw new IllegalArgumentException ();
K[] temp = (K[]) new Comparable[capacity];
for (int i = 1; i <= N; i++) temp[i] = pq[i];
pq = temp;
}
@SuppressWarnings("unchecked")
/** Create an empty priority queue with the given initial capacity, using the given comparator. */
public MinPQ(int initCapacity, Comparator<? super K> comparator) {
pq = (K[]) new Comparable[initCapacity + 1];
N = 0;
this.comparator = comparator;
}
/** Create an empty priority queue with the given initial capacity. */
public MinPQ(int initCapacity) { this(initCapacity, null); }
/** Create an empty priority queue using the given comparator. */
public MinPQ(Comparator<? super K> comparator) { this(1, comparator); }
/** Create an empty priority queue. */
public MinPQ() { this(1, null); }
/**
* Create a priority queue with the given items.
* Takes time proportional to the number of items using sink-based heap construction.
*/
public MinPQ(K[] keys) {
this(keys.length, null);
N = keys.length;
for (int i = 0; i < N; i++)
pq[i+1] = keys[i];
for (int k = N/2; k >= 1; k--)
sink(k);
//assert isMinHeap();
}
/** Is the priority queue empty? */
public boolean isEmpty() { return N == 0; }
/** Return the number of items on the priority queue. */
public int size() { return N; }
/**
* Return the smallest key on the priority queue.
* @throws java.util.NoSuchElementException if the priority queue is empty.
*/
public K min() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}
/** Add a new key to the priority queue. */
public void insert(K x) {
// double size of array if necessary
if (N >= pq.length - 1) resize(2 * pq.length);
// add x, and percolate it up to maintain heap invariant
pq[++N] = x;
swim(N);
//assert isMinHeap();
}
/**
* Delete and return the smallest key on the priority queue.
* @throws java.util.NoSuchElementException if the priority queue is empty.
*/
public K delMin() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
exch(1, N);
K min = pq[N--];
sink(1);
pq[N+1] = null; // avoid loitering and help with garbage collection
if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);
//assert isMinHeap();
return min;
}
/* *********************************************************************
* Helper functions to restore the heap invariant.
**********************************************************************/
private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}
/* *********************************************************************
* Helper functions for compares and swaps.
**********************************************************************/
private boolean greater(int i, int j) {
if (comparator == null) {
return pq[i].compareTo(pq[j]) > 0;
}
else {
return comparator.compare(pq[i], pq[j]) > 0;
}
}
private void exch(int i, int j) {
K swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
// is pq[1..N] a min heap?
private boolean isMinHeap() {
return isMinHeap(1);
}
// is subtree of pq[1..N] rooted at k a min heap?
private boolean isMinHeap(int k) {
if (k > N) return true;
int left = 2*k, right = 2*k + 1;
if (left <= N && greater(k, left)) return false;
if (right <= N && greater(k, right)) return false;
return isMinHeap(left) && isMinHeap(right);
}
/* *********************************************************************
* Iterator
**********************************************************************/
/**
* Return an iterator that iterates over all of the keys on the priority queue
* in ascending order.
* <p>
* The iterator doesn't implement <tt>remove()</tt> since it's optional.
*/
public Iterator<K> iterator() { return new HeapIterator(); }
private class HeapIterator implements Iterator<K> {
// create a new pq
private MinPQ<K> copy;
// add all items to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
if (comparator == null) copy = new MinPQ<K>(size());
else copy = new MinPQ<K>(size(), comparator);
for (int i = 1; i <= N; i++)
copy.insert(pq[i]);
}
public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }
public K next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
void showHeap() {
for (int i = 1; i <= N; i++)
StdOut.print (pq[i] + " ");
StdOut.println ();
}
/**
* A test client.
*/
public static void main(String[] args) {
MinPQ<String> pq = new MinPQ<>(100);
StdIn.fromString ("10 20 30 40 50 - - - 05 25 35 - - - 70 80 05 - - - - ");
while (!StdIn.isEmpty()) {
StdOut.print ("pq: "); pq.showHeap();
String item = StdIn.readString();
if (item.equals("-")) StdOut.println("min: " + pq.delMin());
else pq.insert(item);
GraphvizBuilder.binaryHeapToFile (pq.pq, pq.N);
}
StdOut.println("(" + pq.size() + " left on pq)");
}
}
TestFinalAnswer.java:
package finalanswer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import stdlib.StdIn;
import stdlib.StdOut;
public class TestFinalAnswer {
public static <Item extends Comparable<? super Item>> boolean isSorted(Item[] a) {
for (int i = 0; i < a.length-1; i++) {
if (a[i].compareTo(a[i+1]) > 0) return false;
}
return true;
}
public static void main(String[] args) {
StdOut.println("*** " + FinalAnswer.yourName() + " ***");
StdOut.println();
Integer[] array = new Integer[12];
Random r = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = r.nextInt(1000);
}
StdOut.println("Array before sorting: " + Arrays.toString(array));
FinalAnswer.minpqSort(array);
StdOut.println("Array after sorting: " + Arrays.toString(array));
StdOut.println("Array is sorted: " + isSorted(array));
StdOut.println();
Queue<String> queue = new Queue<String>();
queue.enqueue("first");
queue.enqueue("second");
queue.enqueue("third");
queue.enqueue("fourth");
StdOut.println("Queue before reversing: " + queue);
FinalAnswer.reverseQueue(queue);
StdOut.println("Queue after reversing: " + queue);
StdOut.println();
double[] frequencies = {110.0, 110.0*1.224, 110.0*1.224*1.224};
ArrayList<Chord> risingChords = FinalAnswer.createRisingChordList(0.2, frequencies, 10);
for (Chord risingChord: risingChords) {
StdOut.println("Playing: " + risingChord);
risingChord.play();
}
StdOut.println();
ArrayList<CTATrain> ctaTrains = new ArrayList<CTATrain>();
StdIn.fromFile("data/CTAdata.txt");
while (!StdIn.isEmpty()) {
int runNumber = StdIn.readInt();
String lineColor = StdIn.readString();
String nextStation = StdIn.readString();
String arrivalTime = StdIn.readString();
ctaTrains.add(new CTATrain(runNumber, lineColor, nextStation, arrivalTime));
}
StdOut.println("--- Trains before sorting ---");
for (CTATrain ctaTrain: ctaTrains) {
StdOut.println(ctaTrain);
}
StdOut.println();
ctaTrains.sort(null);
StdOut.println("--- Trains after sorting by run number ---");
for (CTATrain ctaTrain: ctaTrains) {
StdOut.println(ctaTrain);
}
StdOut.println();
ctaTrains.sort((CTATrain t1, CTATrain t2) -> (t1.getArrivalTime().compareTo(t2.getArrivalTime())));
StdOut.println("--- Trains after sorting by arrival time ---");
for (CTATrain ctaTrain: ctaTrains) {
StdOut.println(ctaTrain);
}
StdOut.println();
StdOut.println("=== " + FinalAnswer.yourName() + " ===");
}
}
Instructions 1. Eclipse, create a package called finalanswer. Copy and place into the package the file TestFinalAnswer.java provided below n the package, create a class called FinalAnswer. All of the static methods you are asked to write will go in this classExplanation / Answer
Class FinalAnswer.java:
package finalanswer;
public class FinalAnswer {
public static <Item extends Comparable<? super Item>> void minpqSort(Item[] a) {
MinPQ<Item> minPQ = new MinPQ<>(a.length);
for(Item i: a) {
minPQ.insert(i);
}
int count = 0;
while(!minPQ.isEmpty()) {
a[count++] = minPQ.delMin();
}
}
}
I don't have the various class imported in your project, hence i can not run the above code, but still as per your description, the given code by me should work fine. In case of any issues, please post comments.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.