Hi,
If I have a binary max heap implemented as a tree, where every node has a parent, left, right and key value. How can I determine the running times of it's operations like insert, delete min, merge? I'm not sure where to start...
Hi,
If I have a binary max heap implemented as a tree, where every node has a parent, left, right and key value. How can I determine the running times of it's operations like insert, delete min, merge? I'm not sure where to start...
Alright, my comp sci knowledge might be a little rusty so anyone can correct me if i miss some details.
So basically the big O notation gives the number of computations (algorithm complexity) for a set of size n.
For ex: for loop on a set of size n, thats n operations (one for each element) so this for loop is O(n) complexity.
Likewise, when you are dealing with a tree, the number of nodes it has is roughly approximated by an exponential. For a complete binary tree, it has roughly $\displaystyle 2^n $ nodes. where n gives you the "depth" of the tree.
So if you want to do an insert, basically you attach the child node to the deepest level of the tree and compare it with its parent. if the child node is greater than its parent swap the parent and child. Now do the aforementioned procedure till the child node reaches its proper place, where its parent node is greater than it. So what is the maximum number of times this can happen? Basically until the child node you attached becomes the root of the tree. so esentially, the depth at which the node is at, is the maximum number of comparisons that can happen. Since a tree has exponential nodes, log(# of nodes) should give a rough estimate of depth, since if we have $\displaystyle 2^n$ nodes then $\displaystyle log_2(2^n) $ is the depth of the tree, so the number of computations that can happen, so the number of operations, if n = number of nodes on the tree, is log(n).
So insert is log(n) complexity.
Use the same sort of reasoning for delete, min, and merge.
so basically if the # of operations you have to do is roughly equal to the depth of the tree, it is always O(log(n))