$2.$ 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 $\backslash$Theta $($log n$)$ 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 O$(1).$ Describe how this additional information will be maintained as records are inserted and deleted, and ensure that the maintenance cost of this information does not alter the time complexity of insert and delete operations.