Results 1 to 2 of 2

Math Help - Help with analysis of binary max heaps implemented as trees

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Help with analysis of binary max heaps implemented as trees

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    388
    Thanks
    80

    Re: Help with analysis of binary max heaps implemented as trees

    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 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 2^n nodes then  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))
    Last edited by jakncoke; February 5th 2013 at 03:33 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. question on binary heaps
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 25th 2013, 05:30 PM
  2. Binary trees
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 4th 2011, 07:43 AM
  3. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 6th 2009, 12:05 PM
  4. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 28th 2009, 02:38 AM
  5. binary trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2006, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum