Page 1 of 1
3. (a) Consider the (Max) Heap below, showing the keys of the items stored within it. Suppose that we carry out the foll
Posted: Sat May 14, 2022 3:45 pm
by answerhappygod
- 3 A Consider The Max Heap Below Showing The Keys Of The Items Stored Within It Suppose That We Carry Out The Foll 1 (56.26 KiB) Viewed 61 times
3. (a) Consider the (Max) Heap below, showing the keys of the items stored within it. Suppose that we carry out the following sequence of operations: Heap- Extract-Max(), Max-Heap-Insert(17), Max-Heap-Insert(16) and Heap-Extract- Max(). What is the order of the remaining) elements after this sequence? [6 marks] 28 25 15 20 11 12 12 (10 28 25 15 20 11 12 9 12 10 (b) The key operations of Heap-Extract-Max() and Max-Heap-Insert() are known to have worst-case running-time (Ig(n)) for a Heap containing n items, in the general case. Suppose we consider the setting of a priority queue, where the items only have a few different options for key values - say {1,2,3} are the only possible key values. Does this change the worst-case running-time for Heap-Extract- Max() and Max-Heap-Insert(), and if so, how? Write a sentence or two to justify your answer (for each operation). [4 marks]