self doubt

Question

time complexity to find the n/2 largest element in max heap ?\

it must be nlogn

Comments

Should be O(n) // Elements need not be deleted, n/2 largest element can be found at maximum n/2 level

Deletion of n/2 largest element will take O(nlogn)

Answer 1

Use Extract Max n/2 times to get n/2th maximum element from the Max Heap... Time  --  O(nlogn)

Answer 2

To find an element in max heap takes O(n) time.

To fing n/2 largest element it also takes O(n) time because it will compare with n/2 elements of the max heap which will take O(n) time only not O(nlogn) as we are not asked to delete the elements from the heap