Use 3 files 1.TopM.java 2.tinyBatch.txt 3MinPQ.java TopM.java program reads a sequence of transactions from standard input; takes a command-line integer m; prints to standard output the m largest transactions in descending order. Modify TopM.java to do the following: 1) Calculate and print the Average of the top M transactions. 2) Calculate the Median of the top M transactions. The median is the middle transaction in the Top M values. If there are an EVEN number of values, then the median is found by taking the mean (average) of the two middlemost numbers. Run your program for the Top 10 and Top 11 values separately and include in your results

tinybatch.txt

Turing 6/17/1990 644.08 vonNeumann 3/26/2002 4121.85 Dijkstra 8/22/2007 2678.40 vonNeumann 1/11/1999 4409.74 Dijkstra 11/18/1995 837.42 Hoare 5/10/1993 3229.27 vonNeumann 2/12/1994 4732.35 Hoare 8/18/1992 4381.21 Turing 1/11/2002 66.10 Thompson 2/27/2000 4747.08 Turing 2/11/1991 2156.86 Hoare 8/12/2003 1025.70 vonNeumann 10/13/1993 2520.97 Dijkstra 9/10/2000 708.95 Turing 10/12/1993 3532.36 Hoare 2/10/2005 4050.20

MinPQ.java

/****************************************************************************** * Compilation: javac MinPQ.java * Execution: java MinPQ implements Iterable { private Key[] pq; // store items at indices 1 to n private int n; // number of items on priority queue private Comparator comparator; // optional comparator /** * Initializes an empty priority queue with the given initial capacity. * * initCapacity the initial capacity of this priority queue */ public MinPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; n = 0; } /** * Initializes an empty priority queue. */ public MinPQ() { this(1); } /** * Initializes an empty priority queue with the given initial capacity, * using the given comparator. * * initCapacity the initial capacity of this priority queue * comparator the order to use when comparing keys */ public MinPQ(int initCapacity, Comparator comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; n = 0; } /** * Initializes an empty priority queue using the given comparator. * comparator the order to use when comparing keys */ public MinPQ(Comparator comparator) { this(1, comparator); } /** * Initializes a priority queue from the array of keys. * Takes time proportional to the number of keys, using sink-based heap construction. * keys the array of keys */ public MinPQ(Key[] keys) { n = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i = 1; k--) sink(k); assert isMinHeap(); } /** * Returns true if this priority queue is empty. * return true if this priority queue is empty; * false otherwise */ public boolean isEmpty() { return n == 0; } /** * Returns the number of keys on this priority queue. * @return the number of keys on this priority queue */ public int size() { return n; } /** * Returns a smallest key on this priority queue. * return a smallest key on this priority queue * throws NoSuchElementException if this priority queue is empty */ public Key min() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // helper function to double the size of the heap array private void resize(int capacity) { assert capacity > n; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i 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 ) pq[i]).compareTo(pq[j]) > 0; } else { return comparator.compare(pq[i], pq[j]) > 0; } } private void exch(int i, int j) { Key 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; int right = 2*k + 1; if (left iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator { // create a new pq private MinPQ 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(size()); else copy = new MinPQ(size(), comparator); for (int i = 1; i pq = new MinPQ(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMin() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); } }

topm - Notepad File Edit Format View Help *Compilation: javac TopM.java *Execution: *Given an integer m from the command line and an input stream where * each line contains a String and a long value, this MinPQ client * prints the m lines whose numbers are the highest. * % java TopM 5 (m+1); while (StdIn.hasNextLine()) { // Create an entry from the next line and put on the PQ String line = stdin. readLine(); Transaction transactionnew Transaction (line); pq. insert(transaction); // remove minimum if m+1 entries on the PQ if (pq.size() > m) pq.delMin); // top m entries are on the PQ print entries on PQ in reverse order StdOut.println(); // print blank line for formatting StackTransaction for (Transaction transaction pq) stack new StackTransaction>(); = stack.push (transaction); for (Transaction transaction: stack) StdOut.println(transaction); topm - Notepad File Edit Format View Help *Compilation: javac TopM.java *Execution: *Given an integer m from the command line and an input stream where * each line contains a String and a long value, this MinPQ client * prints the m lines whose numbers are the highest. * % java TopM 5 (m+1); while (StdIn.hasNextLine()) { // Create an entry from the next line and put on the PQ String line = stdin. readLine(); Transaction transactionnew Transaction (line); pq. insert(transaction); // remove minimum if m+1 entries on the PQ if (pq.size() > m) pq.delMin); // top m entries are on the PQ print entries on PQ in reverse order StdOut.println(); // print blank line for formatting StackTransaction for (Transaction transaction pq) stack new StackTransaction>(); = stack.push (transaction); for (Transaction transaction: stack) StdOut.println(transaction)