The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Kth Largest element in MinHeap
+1
vote
436
views
What is the time complexity to find the Kth largest element in a MinHeap?
Or equivalently, What is the time complexity to find Kth smallest element in MaxHeap?
algorithms
heap
binaryheap
timecomplexity
sorting
asked
Dec 1, 2018
in
Algorithms
by
gmrishikumar

436
views
answer
comment
0
I think its O(n) because you have to go through the N/2 to N part of the heap.
+1
Yeah, the nth largest element will be present in one of the leaf nodes, which will take $O(n)$
+1
Yes, It will be O(n).
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
+1
vote
Best answer
The nth largest element will be present in one of the leaf nodes, and will take O(n/2) time to find.
Therefore O(n) is the required complexity.
answered
Dec 1, 2018
by
gmrishikumar
comment
0
Suppose the min heap has elements 1,2,3,4,5 ,6 in that order . And we want to find 4th largest element.
How can you say the 4th largest element will be present in the leaves.?
0
I am not saying that all elements are present in the leaves. Obviously some elements will not be leaves and will be Kth largest element in heap. If element is not in the leaves we won't need O(n) time. We will need less than that.
But if the element is present in the leaf nodes we will need O(n/2) time and hence time complexity is O(n).
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
+6
votes
3
answers
1
7th smallest element in a MinHeap
In a minheap with n elements 1). The 7th smallest element can be found in time, if duplicates are allowed ? 2). The 7th distinct smallest element can be found in time, If duplicates are allowed ?
asked
Sep 4, 2016
in
Algorithms
by
Kapil

1.6k
views
algorithms
heap
binaryheap
sorting
timecomplexity
0
votes
0
answers
2
Data Structure: Find 7th smallest element in Min heap
In a binary min heap with n elements, the 7th smallest element can be found in _____ ? Answer given is O(logn) and solution: Delete the 1st smallest element O(logn) Delete the 2nd smallest element O(logn) .... ... this solution the data arrangement of the heap will be changed after performing these operation. any better solution than this???
asked
Oct 18, 2017
in
Programming
by
Shubhanshu

556
views
heap
binaryheap
timecomplexity
algorithms
+9
votes
6
answers
3
What is the complexity of finding 50th smallest element in an already constructed binary minheap?
asked
Dec 28, 2014
in
Algorithms
by
Vikrant Singh

1.2k
views
algorithms
binaryheap
heap
0
votes
0
answers
4
No. of comparison in min heap
What is the number of comparisons required to extract 45th element of the min heap?
asked
Sep 10, 2018
in
Algorithms
by
bts1jimin

541
views
algorithms
heap
binaryheap
timecomplexity
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
Recent Posts
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
IIT Tirupati MS Interview 2020
IIT Bombay Mtech RA  interview experience (2020)
Subjects
All categories
General Aptitude
2k
Engineering Mathematics
8.2k
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent Blog Comments
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
ISI 2019 : Aarushi Aiyyar's answer to How do...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,315
questions
60,436
answers
201,777
comments
95,257
users