1 1 vote What is the time complexity of 'deleting any random node from a max or min heap'? Data Structures binary-heap time-complexity data-structures + – Avijit Shaw 5.3k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 9 9 votes 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))$ Shobhit Joshi answered Dec 21, 2018 • selected Dec 21, 2018 by Avijit Shaw Shobhit Joshi comment Share Follow See all 6 Comments 6 6 Comments reply Avijit Shaw commented Dec 21, 2018 reply Follow flag Thanks 0 0 replyShare Shaik Masthan commented Dec 21, 2018 reply Follow flag 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) 4 4 replyShare Magma commented Dec 21, 2018 reply Follow flag 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 0 replyShare Shaik Masthan commented Dec 21, 2018 reply Follow flag @Magma how can you find an element with in O(log n) time in HEAP ? 0 0 replyShare Avijit Shaw commented Dec 21, 2018 reply Follow flag True, searching takes O ( n) time in heap . 0 0 replyShare Magma commented Dec 21, 2018 reply Follow flag O sorry bad mistake 0 0 replyShare Please log in or register to add a comment.
