Suppose we we are reading an input stream of N numbers, and after reading the stream, we want to report the M largest numbers. Suppose M is big, but relatively small compared to N: M N/ lg N. For both parts, describe how to solve the problem using a binary heap. (One of these is TopM in the book, for the other you need the linear-time heap construction method of Section 2.4, part of the discussion of heapsort.)

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. Remarks: In both parts, space counts words of memory. A word is large enough to store an input number, an index,