what is the time complexity of deleting any node from the heap
Time complexity
hello @shashankmaheshwari054
To delete any random node. first we have to find it which is O(N) and then we have to delete it by using heapify which is log(n)
so in total it is O(N+ LOG N )
after heapify the deletion will also take O(logn)
once we have found the node that we want to delete then we need to bring it on the top of heap for that we need to use hepify up function which will take log(n) and after that we simply remove it from the top.
so the deletion complexity = time to found + time to bring it on top and delete
-> N + LOG N
-> o(N+ log N)
but if we directly delete it from the top are heap will not get disturbed
so we have to swap it with last index and then do down heapify
yeah . . . . . . . .that is the procedure after bringing data(to be deleted) on the top
so this process will aslo take O(log n)
yeah , up and down heapfiy both takes o(logN)
so the complexity should be=O(n+logn+logn)
Yeah its the same thing
o(N + C * LOGN)-> o(N+LOGN) -> O(N) (IGNORED LOWER term)
i think writing this O(n+logn) this is also correct in terms of big O notation
yeah . . . . . . . . . . . .
could u suggest me when to do leetcode should i start now only or after completing the whole course
practice in parallel.
whatever topic u r learning from course ,practice it from leetcode(or any site that u prefer)
for some guidance can you give your number or its not allowed here
its showing no results found
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.