Heapsort

Show that, with array representation for storing an n-element heap, the leaves are the nodes indexed by [n/2]+1, [n/2]+2.n. (2 points)

Show that each child of the root of an n-node heap is the root of a subtree containing at most 2n/3 nodes. What is the smallest constants such that each subtree has at most n nodes? (2 points)

The operation MAX-HEAP-DELETE (A, x) deletes the object x from the max-heap A. Give an implementation of MAX-HEAP-DELETE for an n-element. Also show the run-time analysis? (2 points)

Quicksort

When RANDOMIZATION_QUICKSORT runs, how many calls are made to the random-number generator RANDOM in the worst case? How about the best case? Give the answers in terms of notation? (2 points)

What value of q does PARTITION return when all elements in the subarray A [p: r] have the same value? Modify the partition so that q= [(p+r)/2] when all elements in the subarray A [p: r] have the same value? (2 points)