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

it must be nlogn
asked in Algorithms by (105 points) | 38 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 (1.7k 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.1k points)

Related questions

0 votes
0 answers
3


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

42,454 questions
48,492 answers
154,710 comments
63,079 users