The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
40 views
time complexity to find the n/2 largest element in max heap ?\

it must be nlogn
asked in Algorithms by (107 points) | 40 views
0
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)

2 Answers

+1 vote
Use Extract Max n/2 times to get n/2th maximum element from the Max Heap... Time  --  O(nlogn)
answered by Active (2.4k points)
+1 vote
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
answered by Active (1.2k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,253 questions
51,482 answers
178,685 comments
66,768 users