Answer the following questions about the properties of heaps and priority queues
ID: 3792062 • Letter: A
Question
Answer the following questions about the properties of heaps and priority queues. a. What is the run time of HEAPSORT on an array in sorted order? Briefly justify. b. What are the minimum and maximum number of elements in a heap of height h? c. Increase-Key defined in 6.5 has an input parameter that is the index of the element being increased. Modify Increase-Key so that only the original key and new key are passed in, thus requiring the algorithm to first find the index of the original key. Assume unique key values. What is the worst-case runtime of this new version of Increase-Key (use Omega, Big-O, or Theta as appropriate)? Briefly justify.
Explanation / Answer
a. When the input array A is in sorted order then the runtime of HEAPSORT will be O(nlogn) for n elements in the
array.
b. The minimum number of nodes possible in a heap of height h is 2h.
The maximum number of elements in a heap of height h is (2^h+1)-1