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

it must be nlogn
asked ago in Algorithms by (95 points) | 30 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)

1 Answer

+1 vote
Use Extract Max n/2 times to get n/2th maximum element from the Max Heap... Time  --  O(nlogn)
answered ago by (121 points)

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

39,535 questions
46,681 answers
57,675 users