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 682 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments 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.