Short answer
Option B — because 9th largest element is asked for.
Min heap is centralized towards smaller elements, so for larger elements, time complexity is never optimal.
For a sorted array, all we need to do is go to the 9th element from the last index. Extract it, then shift 8 elements one position to the left. This takes constant time.
For balanced BST, the largest element is the rightmost element. Combine that with the fact that the tree is balanced, we get logarithmic time complexity.
Long Answer
find and remove the 9th largest element
First of all, note that Time Complexity is a theoretical concept, and there's a world of difference between "9th largest" and "kth largest"
Let's see this question for both 9th largest, and kth largest — for each data structure given. Along with a few other variations.
Min heap
In a min heap, we know only three things:-
- Root has the smallest element.
- Root of a subtree has the smallest element of that subtree. Both these points are the definitions of "heap property"
- The nth smallest element will be found in the first n levels of the min heap.
(For max heap, all the points apply for "largest" instead of smallest)
So, do we know anything about the largest element in a min heap? Other than the fact that it will be a leaf node (can be derived from heap property), we can't say anything more.
The 9th largest element will be in any random location, as long as it doesn't violate heap property. This will take O(n) time. Same would be for the case of kth largest element.
PS: If this was a max heap, then by point number 3, we know that 9th largest element will be present in the first 9 levels. So, finding the 9th largest element in any max heap takes $O(1)$ time. Because no matter how big the heap is, we'll search for only first 9 levels.
Sorted Array
In a sorted array of n elements, all we need to do is go to the 9th element from the last index. Extract it, then shift 8 elements one position to the left. This takes $O(1)$ time.
But if this was kth largest, then we'd have needed to go to the kth element from the right, extract it, and move $(k-1)$ elements to the left. This would take $O(k)$ time.
For the smallest element, we would extract the element at the first index (index number 0) and move the remaining $(n-1)$ elements by one position to the left. This takes $O(n)$ time.
Keep in mind this we're doing this rearrangement because we need to find and remove the required element.
Balanced Binary Search Tree
This is a bit tricky. But any problem related to Balanced Binary Search Tree should be solved by keeping this fact in mind that to find any specific node, we need $O(logn)$ time.
We'll get the largest element in $O(logn)$ time. Remove it, and re-adjust: $O(logn)$ time.
So, total time to find and remove the largest element: $O(logn+logn)=O(logn)$
If we do this 9 times, we get $O(18logn)=O(logn)$ time.
Obviously, this algorithm rips apart your tree, and is meant to be used just once. Or you can add back the 9 elements, again in $O(9logn)=O(logn)$ time.