Question

Assume that your machine has a built-in data structure that inserts an item into a priorityqueue in one step. There is no charge to remove an item. It has both a min-priority queue anda max-priority queue available. You can access the largest element for one comparison step ina max-priority queue, and similarly you can access the smallest element for one comparisonstep in a min-priority queue.

This machine can sort a list in linear time: Insert all of the elements into a priority queue andthen remove them (one at a time). This isnqueue inserts and no comparisons, for list of sizen.

What if your priority queue is restricted to having sizes? You can assume that your algorithmmay have many different priority queues (but each can have size at mosts). You can distinguishelements in the priority queue (perhaps by their original index in the list).

(a) i. Design an efficient algorithm based on merge sort. You may describe it in high levelEnglish or in pseudo code, but the algorithm must be clear.

ii. Analyze its time: Give the number queue inserts and number of comparisons as pre-cisely as reasonably possible. At least give the high order term exactly. Your answer should be a function of the list size,n, and the queue size,s.

(b) i. Design an efficient algorithm based on heapsort. You may describe it in high levelEnglish or in pseudo code, but the algorithm must be clear.

ii. Analyze its time: Give the number queue inserts and number of comparisons as pre-cisely as reasonably possible. At least give the high order term exactly. Your answer shoul be a function of the list size,n, and the queue size,s.

Answer 1