The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
88 views

Let's say we're given with a MAX Heap and we want to delete any of the leaf node, then how much time will it take to delete any of the leaf node and maintain the max heap property?

 

My main doubt is - will it O(n) time to reach to leaf nodes?

 

asked in DS by Loyal (9.4k points) | 88 views
0
max heap tree is given, so no need to check max heap property again

$O(logn)$ will be sufficient
0

@srestha  Time taken to find the leaf node?

 

+1
To find that particular leaf element O(n)

To maintain heap property O(log n)

Total O(n)
0

Tesla! Thanks buddy! and thank you srestha Ma'am.

+1

we want to delete any of the leaf node

$O(1)$ will suffice for deleting any leaf node(If you are asked to delete any leaf node and not some specific leaf node)...Just delete the last element. 

1 Answer

+2 votes
Best answer
Heap is nothing but an array with heap property. So If you wish to delete just $any$ leaf node, then Just delete the last element of the Heap and it will take just $O(1)$ time since It is an array and you can go to the last element in $O(1)$ time.
answered by Boss (21.8k points)
selected by
0
And how about a particular leaf node apart from last leaf node?
0
previous of last node , is also a leaf node
0

And how about a particular leaf node apart from last leaf node?

There are approx $\frac{n}{2}$ leaves in the Heap. So, If we wish to delete some Specific leaf node then first we would have to find it, which could take $O(n) $ time itself. Then after finding that leaf we can delete that node in just $logn$ time. 

0

previous of last node , is also a leaf node

Wouldn't be true if $n=2$ 

0
then also $O(1)$ if $n=2$

if $n>2$ then too $O(1)$
0

There are approx n2 leaves in the Heap. So, If we wish to delete some Specific leaf node then first we would have to find it, which could take O(n) time itself. Then after finding that leaf we can delete that node in just logn time. 

 

So, it's O(n) * O (logn) = O(n), right?

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

47,005 questions
51,324 answers
177,496 comments
66,668 users