Problem 3. Suppose we we are reading an input stream of N numbers, and after reading 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.

3(a). Solve the problem in O(N) time and O(N) space.

3(b). 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.