Suppose you have a list of integers Zo, ,..., n. You would like to produce a duplicate-free list, although you're not picky about changing the order of items, so for example if the input is [1,3,5, 3, 2] then a perfectly acceptable output is [5, 2, 3, 1]. (a) [10 points] Explain how to do so in O(n log n) time in the worst case. (b) [10 points] Explain how to do so in O(n) time "on average" (or "with high probability", or however else you like to say). Problem 3. Merging Binary Heaps [20 points] Suppose you have two binary heaps h and h, and you wish to produce a new heap h that combines both of them. That is, h contains all of the items (& their priorities) from both hi and h. Suppose that h and h have m and n elements, respectively. (a) [5 points] Explain how to do so in O(n +m) time. Justify your claim. (b) [10 points] Suppose n < m. Explain how to do so in O(n log m) time. Justify. (c) [5 points] Develop a combined merging strategy that will run in O(min{n+m, n log m,m log n}) time. You can assume the existence of the strategies in (a) and (b), even if you haven't figured them out yourself.