1. Engineering
  2. Computer Science
  3. i believe part a should be utilizing a priority queue...

Question: i believe part a should be utilizing a priority queue...

Question details

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 Nitemspublic class TopM public static void main(String[] args) // Print the top M 1ines in the input stream. int M Integer.parseInt (args[0]) MinPQ<Transaction> 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. Stack«Transaction» stack = new Stack«Transaction»(); while (pq.isEmptyO) stack.push (pq.delMinO); for (Transaction t stack) StdOut.println(t)public static void sort (Comparable [] a) int N - a.length; for (int k - N/2; k >- 1; k--) sink (a, k, N); while (N> 1) exch (a, sink (a, 1, 1, N--); N);

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

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution