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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Deleting a random node from Heap
+1
vote
216
views
What is the time complexity of 'deleting any random node from a max or min heap'?
heap
binaryheap
timecomplexity
datastructure
asked
Dec 21, 2018
in
DS
by
Avijit Shaw
(
125
points)

216
views
answer
comment
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
Please
log in
or
register
to answer this question.
1
Answer
+2
votes
Best answer
The deletion of a random node would take $O(n+log(n))$ as first we will find where the random element is in the heap which will take $O(n)$ and then delete it which will further take $O(log(n))$
answered
Dec 21, 2018
by
Shobhit Joshi
Active
(
5.1k
points)
selected
Dec 21, 2018
by
Avijit Shaw
comment
0
Thanks
+1
Find the node which has to be delete, decrease the key to INF (in case of min heap), now your element is at root position, Now apply Extract MIN operation.
∴ O(n) + O(log n) + O(log n) = O(n)
0
I think it's O( log n)
To finding a element in a min heap : O ( logn)
Then apply deletion takes : O ( log n)
0
@Magma
how can you find an element with in O(log n) time in HEAP ?
0
True, searching takes O ( n) time in heap .
0
O sorry
bad mistake
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
0
votes
1
answer
1
Finding the minimum element in a Heap
I was going through the heap concept and one question came into my mind what will be the best case time complexity of finding the minimum element in a max heap? Thank you:)
asked
Jan 15
in
DS
by
Nandkishor3939
Active
(
1.1k
points)

185
views
heap
binaryheap
timecomplexity
0
votes
0
answers
2
Heap Sorting
Consider a binary tree, where left and right subtreealready heapified. But we havenot done heapificationfor root yet. Then what is time complexity to convert it in a full heap tree? $A)O(\log n)$ or $o(n)$ $B)\Omega (\log n)$ or $\omega(n)$ $C)\Theta (\log n)$ or $\theta (n)$ $D)\text{None of these}$
asked
Aug 18, 2018
in
DS
by
srestha
Veteran
(
112k
points)

160
views
algorithms
sorting
heap
binaryheap
timecomplexity
+6
votes
3
answers
3
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
Veteran
(
50.3k
points)

1.3k
views
algorithms
heap
binaryheap
sorting
timecomplexity
0
votes
0
answers
4
Max heap when stored in an array is always in sorted order
This question is in CLRS,if we have a max heap it is always in sorted order(descending) order.And by extension if we have min heap the array is sorted in ascending order.Is this true? I have a counter example for ... it an heapified representation or not? If we heapify after deletion and store max deleted element then we get sorted array.
asked
Nov 15, 2018
in
DS
by
sripo
Active
(
2.3k
points)

173
views
sorting
binaryheap
arrays
heap
datastructure
algorithms
0
votes
0
answers
5
#DS Inserting elements into Min Heap?
The number of distinct min heap are possible with keys 1, 2, 3, 4, 5 are ________. I know, there are variance of this question for Max heap and even for Min heap, the answer won't change, but I just wanna know if my technique is right or not. ===== ... any value. > Lastly the right sub tree => 1C1 = 1 Totally  1*4C3*1*2*1 = 8. Is this approach correct?
asked
Jun 24, 2018
in
DS
by
iarnav
Loyal
(
7.9k
points)

113
views
algorithms
binaryheap
heap
datastructure
+1
vote
0
answers
6
Number of Max Heap
How many maxheaps can be formed with the following elements? $\{1,1,1,2,2,2,3,3,3,4,4,4\}$
asked
Jun 4, 2018
in
DS
by
Balaji Jegan
Active
(
4.8k
points)

366
views
datastructure
permutationandcombination
binaryheap
heap
+1
vote
2
answers
7
Max Heap
The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into binary heap. Such that resulted binary heap is max heap ________.
asked
Nov 7, 2017
in
DS
by
shivangi5
Active
(
1.1k
points)

445
views
heap
binaryheap
datastructure
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
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
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Digital Logic
2.9k
Programming and DS
4.9k
Programming
3.6k
DS
1.3k
Algorithms
4.4k
Theory of Computation
6k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.4k
Others
1.5k
Admissions
595
Exam Queries
577
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent Blog Comments
there's way to know this...
@Arjun Will it be possible to add if a question...
First of all congratulations and please write...
i did not get any address confirmation mail...
How did you deal with stress periods as you...
49,784
questions
54,511
answers
188,329
comments
75,114
users