The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
105 views

asked in Algorithms by Loyal (10k points) | 105 views
0

1 Answer

+1 vote
Best answer

yes all are correct!

In first case to find the kth largest element, do k-1 deletions from the max heap, so k-1 times max-heapify procedure will be called.

T.C (k-1)logn = O(klogn)

answered by Boss (42.7k points)
selected by
0

@Manu,

for (ii), i think it will take O(n+klogn)........

since n/2 minimum elements are present in leaves of a max heap, now you have to find kth minimum among them, you can work it like this,

create min heap for that n/2 elements -> O(n)

perform extract_min for k times -> O(klogn)

in total it will take-> O(n+klogn), though if k is some constant, answer will be O(n), but in worst case k can be of O(n)..

therefore i think in worst case to find kth min in max heap will take -> O(n+klogn)

0
and also one more thing, it might be case that kth min is not even in leaf, because leaf contains about n/2 keys, what if it is saying to find (n/2+5)th minimum..
0
@Manu Thakur,  Got it.. Thanks a lot :)
0
@nitish yes you are right answer should b O(n + klogn)

but they explicitly mentioned that k is less than n, and if we believe that it's some constant and n value is huge, we can go for O(n) T.C
0
but less than doesn't mean that it is some constant, k could be {n-4, n-6 , n/2 , n/4}, all these values are <n and also even O(n)
0

for that case take all n elements of max heap and build a min heap...and then perform kth min. operation...

T(n)=O(n)+O(klogn) 

0
@nitish i am not denying this possibility what you said.
0
@hs_yadav

yes, exactly i was also saying this...in worst case it will take O(n+klogn)..

it will take O(n) time only when in qsn it is explcitly mentioned that k is some constant.
0
@Manu

most appropriate answer then should be (i) and (iii) only...isn't it??
0
Option (ii) is also okay as K is less than number of element
0
@Sandeep Suri

please read above comments first.
0
It's looking for a minimum element in a MAX Heap. Why are you deleting the items here and heapifying again?

In any case it should take maximum O(n) T.C

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
48,756 questions
52,850 answers
183,548 comments
68,742 users