As we saw in our discussion of QuickSelect, the selection problem asks us to determine the kth

largest element out of a sequence of elements. In this problem, we will consider this problem in the

context of trees.

a$.(5$ pts$)$ Propose an algorithm that uses a heap to determine the kth largest element in an unsorted

sequence of elements. State the time complexity of this algorithm using Big Theta notation and prove

your result. Assume that k is not a constant, and must be considered within this analysis $($i$.$e$.,$ your

cost function should be T$($n$,$ k$)).$ Describe briefly how the different terms in your complexity bound

relate to the operations performed by this algorithm.

b$.(5$ pts$)$ Extend your solution to the above problem into a fully general sorting algorithm. Prove the

time and space complexity of this algorithm using Big Theta notation.

c$.(15$ pts$)$ Assuming that your data is stored in a balanced binary search tree, propose an algorithm for

determining the kth largest element in time and prove its correctness and time complexity

bounds. You may augment the nodes of the tree with additional information, so long as the additional

space complexity $($i$.$e$.,$ the cost of your additional data, not counting the cost of the tree itself$)$

remains $.$