I believe part a should be utilizing a priority queue to get the binary heap, and part b should utilize heapsort.

Problem 3. the stream, we want to report the M = N largest numbers from the stream. For both parts. describe how to solve the problem using a binary heap. (One of these is "TopM" in your book, pages 310-311. For the other, you need to use the linear-time heap construction method of Section 2.4, the first phase of heapsort, and you need to argue M lg N -O(N).) Suppose we we are reading an input stream of N numbers, and after reading 3(a). 3(b). Solve the problem in O(N) time and O(N) space Solve the problem in O(N lg M) time and O(M) space. Remark: In one part you can refer to the book, in the other you need to present a new algorithm. English or pseudocode is enough, you do not have to use Java. Be clear about whether you need a "min" heap or a "max" heap. "Space" counts words of memory, where a word is large enough to store an input number, an index, or a reference. These two solutions demonstrate a "trade-off" between time and space. order of growth time client space Nlog N N sort client PQ client using elementary implementation PQ client using heap-based implementation NM Nlog M M Costs of finding the largest M in a stream of Nitems public class TopM public static void main(String[] args) // Print the top M 1ines in the input stream. int M Integer.parseInt (args[0]) MinPQ pq new MinPQTransaction> (M+1); while (StdIn.hasNextLineO) // Create an entry from the next line and put on the PQ. pq.insert (new Transaction (StdIn.readLineO)) if (pq.size) > M) pq.delMin // Remove minimum if M+1 entries on the PQ Top M entries are on the PQ. StackTransaction stack = new StackTransaction(); while (pq.isEmptyO) stack.push (pq.delMinO); for (Transaction t stack) StdOut.println(t)