Question about heap data structures and aIgorithms Please ex

Question about heap data structures and aIgorithms:

Please explain

If a new heap data structure was created that allowed inserting elements into a heap in theta(1) while also allowing the maximum element to be popped in theta(1), what would the runtime of heap sort be with this new data structure? Theta(nlg(n)) Theta(n) Theta(lg(n)) Theta(n^2)

Solution

The correct answer is (n log(n))

Explanantion:

heapsort\'s running time is O(n lg n). Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time.