Heap - Heapify complexity

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

  • 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.

Howdy, Stranger!

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

Categories

In this Discussion