Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Heap - Heapify complexity

z0rgyz0rgy Member Posts: 1
Hi,
Im having trouble in understanding how a heaps children subtree can have
at most 2n/3 nodes. Could someone please explain?
im talking about a binary tree heap. Filled from left to right.

Comments

  • bubbatremellbubbatremell Member Posts: 39
    Well, we can understand 2n/3 to be 2/3 of the total nodes. So what you need to look for is when the ratio between subtree nodes and all nodes is the greatest.
    Because it's a binary heap, we know that for a tree of size n (where a tree with one node is height 1), a full tree will have
    2^n - 1 nodes.
    Now, assume we have the greatest possible subtree on the left. It will be height n-1 and have 2 ^ n-1 - 1 nodes. Since the left subtree has the max ratio of nodes possible, the right subtree must have the minimum ratio possible, which means its height is n - 2. The overall tree can be thought of as the sum of the left sub tree, the right sub tree, and the root. That gives us
    left + right + root = 2^n-1 -1 + 2^n-2 -1 + 1 = total
    The left subtree is still left = 2 ^ n-1 -1.
    So, now we just need to discover the max ratio of left/total. Much like the right subtree, my interest in doing the math for that right now is minimal, so I wrote python code to do it for me.
    [code]
    >>>def full_subtree(x):
    return 2**(x-1) - 1

    >>>def ratio(x):
    return full_subtree(x-1) / float(full_subtree(x-1) + full_subtree(x-2) + 1)

    >>>for x in range(3, 30):
    ratio(x)
    0.5
    0.59999999999999998
    0.63636363636363635
    0.65217391304347827
    0.65957446808510634
    0.66315789473684206
    0.66492146596858637
    0.66579634464751958
    0.66623207301173404
    0.66644951140065145
    0.66655812438944972
    0.6666124043626892
    0.66663953772279649
    0.66665310274669376
    0.66665988484466232
    0.66666327579015905
    0.66666497123703627
    0.66666581895400734
    0.66666624281087594
    0.66666645473890607
    0.66666656070282004
    0.66666661368475177
    0.66666664017571131
    0.66666665342118947
    0.66666666004392827
    0.66666666335529745
    0.66666666501098204
    [/code]
    Not a rigorous proof, but it demonstrates the point.
Sign In or Register to comment.