Heapsort algorithm

[ngolehung84]

Hi everyone,

In this document:
http://www.cs.vassar.edu/~cs241/BHProof.pdf

Theorem 1

"There are at most ceiling(n/2power(h+1) nodes of height h in any n-element heap"

I tried with n=10 (height of tree is 3) and h=1 but the result is 3. But in this case, we can see at height 1, the number of node is 4.

Where did I misunderstand the above statement?

Thank you very much.

[TheCPUWizard]

Hi everyone,

In this document:
http://www.cs.vassar.edu/~cs241/BHProof.pdf

Theorem 1

"There are at most ceiling(n/2power(h+1) nodes of height h in any n-element heap"

I tried with n=10 (height of tree is 3) and h=1 but the result is 3. But in this case, we can see at height 1, the number of node is 4.

Where did I misunderstand the above statement?

Thank you very much.

See highlighted text.

[ngolehung84]

Hi,
"At most" means "no larger than" (if my English is right).
In this case, using the above formula, at most = 3 for height 1. But when you build the heap from 10-element array, you get four element at the height 1. That's the problem.

If this is "at least", everything will be fine for this particular case.

Thanks.

[TheCPUWizard]

You CAN'T have 4 nodes at (h=1) with 10 nodes.

If you have 4 at (h=1), you must have at least 4 at (h=0), your must have 2 at (h=2) and 1 at (h=3)


This is an 11 node tree...

[ngolehung84]

I don't think we cannot have 10-element heap. You can create an array with 10 elements and then build a heap. You can get 10-node heap. You can find the 10-node heap in some book. I'm using the "Introduction to Algorithm" book.

Even if you have 11 node tree, you still have the problem because ceiling(n/2power(2h+1)) = 3 at height 1 while that heap has four elements at height 1. That's still the same problem.

I think maybe they don't make clear that this is the full heap (just maybe, I'm still looking for the logical answer).

Thanks.

[TheCPUWizard]

I don't think we cannot have 10-element heap. You can create an array with 10 elements and then build a heap. You can get 10-node heap. You can find the 10-node heap in some book. I'm using the "Introduction to Algorithm" book.

Of course you can have a heap with 10 nodes,.


Even if you have 11 node tree, you still have the problem because ceiling(n/2power(2h+1)) = 3 at height 1 while that heap has four elements at height 1. That's still the same problem.

I think maybe they don't make clear that this is the full heap (just maybe, I'm still looking for the logical answer).

Thanks.

I will put together a short document later today showing why YOUR math (not the poof) is wrong....

[ngolehung84]

I just don't understand that why the statement is wrong when I try with the particular case: n=10 (10-element heap) and h=1 (at height = 1). So maybe I misunderstood something in that statement.

Thank you very much, TheCPUWizard. Hope you post your documents asap.

[ngolehung84]

Have you found the document yet, TheCPUWizard?? I have been waiting so long :(

[TheCPUWizard]

I did not get a chance to find the paper I was looking for, but I think I know the source of your confusion.....

Remember that this only applies to "complete" trees. A complete tree ALWAYS has an odd number of nodes, all internal nodes have exactly 2 children.

Instead of looking at "h", lets look at "d".

D=max depth of tree
d= D - 1

So
d = 1 : 1 node
d = 2 : 1 node + 2 child nodes
d = 3 : 1 node + 2 child nodes + 4 grandchild nodes
d = 4 : 1 node + 2 child nodes + 4 grand + 8 great grand

Since (d=4) requires at least 15 nodes, we know that d=3 when n=11.

Now lets look at what happens to lead (L)nodes, based on (n).

n = 7; d = 3; L= 4.

therefore:
N(h=0) = 4
N(h=1) = 2
N(h=2) = 1

We add a single node (n=8). This is going to make one of the leaf nodes an internal node, so the number of leaf nodes stays the same.

If were were to add two nodes (n-9). One of the existing leaf nodes would be become an internal node, resulting in a net add of one internal, and one leaf.

The promotion of a node from leaf to internal (taken alone) causes h(1) to be increased by one, but ALSO causes the parent to be promoted from h(1) to h(2).

This is shown in the following graph:

A
B B
C C C C
D D D D


Here we have 12 nodes, which is the maximum that can be achieved before the "last leaf" gets promoted. There are still only 3 nodes with h=1


A
B B
C C C C
D D D D


Since 2^(h+1) for h=1 is 4, we still get 12/4=3.....

Make sense????

[ngolehung84]

ya, if it is full heap, it is right. I ask this question because in th book, they use the word "for any tree"

[TheCPUWizard]

ya, if it is full heap, it is right. I ask this question because in th book, they use the word "for any tree"

Look carefully:

in a proper binary tree T (where every internal node has 0 or 2 children)


Additionally the "h" calculation for improper trees is a bit more complicated. And in many circles there is not agreement.

If a node at an arbitrary point in the tree has one child, it can be considered a leaf or an internal (depending on which "side" of the node you look at).

[ngolehung84]

Thank you very much, TheCPUWizard.