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

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

No related questions found

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
50,121 questions
53,242 answers
70,481 users