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