0 votes 0 votes 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? DS binary-heap + – iarnav asked Jun 19, 2018 iarnav 706 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply srestha commented Jun 19, 2018 reply Follow Share max heap tree is given, so no need to check max heap property again $O(logn)$ will be sufficient 0 votes 0 votes iarnav commented Jun 19, 2018 reply Follow Share @srestha Time taken to find the leaf node? 0 votes 0 votes Tesla! commented Jun 19, 2018 reply Follow Share To find that particular leaf element O(n) To maintain heap property O(log n) Total O(n) 1 votes 1 votes iarnav commented Jun 19, 2018 reply Follow Share @ Tesla! Thanks buddy! and thank you srestha Ma'am. 0 votes 0 votes Deepak Poonia commented Jun 19, 2018 reply Follow Share 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. 2 votes 2 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes 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. Deepak Poonia answered Jun 19, 2018 • selected Jun 20, 2018 by srestha Deepak Poonia comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Deepak Poonia commented Jun 20, 2018 reply Follow Share previous of last node , is also a leaf node Wouldn't be true if $n=2$ 0 votes 0 votes srestha commented Jun 20, 2018 reply Follow Share then also $O(1)$ if $n=2$ if $n>2$ then too $O(1)$ 0 votes 0 votes iarnav commented Jun 21, 2018 reply Follow Share 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? 0 votes 0 votes Please log in or register to add a comment.