[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

on an n-element heap and its nodes of height h

Daniel Bastos

4/18/2016 11:49:00 AM

I wonder if anyone can show me intuitively that an n-element heap can
have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
any idea that help me see this. Thank you!
13 Answers

Wally W.

4/18/2016 12:09:00 PM

0

On Mon, 18 Apr 2016 08:48:44 -0300, Daniel Bastos wrote:

>I wonder if anyone can show me intuitively

If it is intuitive, it doesn't need to be shown.

>that an n-element heap can
>have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
>any idea that help me see this. Thank you!

Sounds like homework.

Maybe the understanding of "intuitive" by programmers explains some of
the crap interfaces.

Maybe they should take English language courses before courses in
programming languages.

Öö Tiib

4/18/2016 12:47:00 PM

0

On Monday, 18 April 2016 14:48:52 UTC+3, Daniel Bastos wrote:
> I wonder if anyone can show me intuitively that an n-element heap can
> have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
> any idea that help me see this. Thank you!

The answer there looks incorrect so I can not show (intuitively or
otherwise) how it is correct. However the math is really simple and
straightforward. Heap is simply a binary tree with certain properties
and so you just have to ask yourself correct questions.

a) What is maximum amount of nodes in binary tree with height (h)?
b) What is maximum amount of nodes in binary tree with height (h - 1)?
c) What is maximum amount of nodes of height (h) in binary tree and
how it is related to answers to a) and to b)?
d) How can binary tree's size in nodes (n) limit answer to c)?

However if you can not answer these questions then the whole issue
can be in no way explained to you because you don't know the
basics.


Richard Heathfield

4/18/2016 1:42:00 PM

0

On 18/04/16 12:48, Daniel Bastos wrote:
> I wonder if anyone can show me intuitively that an n-element heap can
> have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
> any idea that help me see this. Thank you!

The intuitive way to think about this is to recognise that a heap is
really a binary search tree in disguise, and shares many of the same
properties. A binary search tree of height h > 0 will have at most
2^(h-1) nodes at its deepest level (and a perfectly-balanced,
perfectly-filled binary search tree will have exactly that many nodes at
that level).

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Daniel Bastos

4/18/2016 4:37:00 PM

0

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 18/04/16 12:48, Daniel Bastos wrote:
>> I wonder if anyone can show me intuitively that an n-element heap can
>> have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
>> any idea that help me see this. Thank you!
>
> The intuitive way to think about this is to recognise that a heap is
> really a binary search tree in disguise, and shares many of the same
> properties. A binary search tree of height h > 0 will have at most
> 2^(h-1) nodes at its deepest level (and a perfectly-balanced,
> perfectly-filled binary search tree will have exactly that many nodes
> at that level).

I'm unable to verify that a search tree of height h > 0 will have at
most 2^(h-1) nodes at its deepest level. Should it be 2^h? (My
reasoning below.)

--8<---------------cut here---------------start------------->8---
A binary search tree of height 0 will have at most 2^0 nodes at its
deepest level.

A binary search tree of height 1 will have at most 2^1 nodes at its
deepest level.

A binary search tree of height 2 will have at most 2^2 nodes at its
deepest level.

A binary search tree of height k will have at most 2^k nodes at its
deepest level.
--8<---------------cut here---------------end--------------->8---

If this is correct, then I'm with you.

Other things I can see: I can see that there'll only be one node whose
height equals the tree height. But if you ask me for a height somewhere
in between the tree-height and height 0, I'm not so sure, but you might
have put me in the right way of thinking. Perhaps I'll catch the idea
if I think more about it.

Thank you very much for your attention.

Daniel Bastos

4/18/2016 4:56:00 PM

0

�ö Tiib <ootiib@hot.ee> writes:

> On Monday, 18 April 2016 14:48:52 UTC+3, Daniel Bastos wrote:
>> I wonder if anyone can show me intuitively that an n-element heap can
>> have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
>> any idea that help me see this. Thank you!
>
> The answer there looks incorrect so I can not show (intuitively or
> otherwise) how it is correct.

Which answer? You lost me here.

> However the math is really simple and straightforward. Heap is simply
> a binary tree with certain properties and so you just have to ask
> yourself correct questions.
>
> a) What is maximum amount of nodes in binary tree with height (h)?

That's 2^0 + 2^1 + 2^2 + ... + 2^h.

> b) What is maximum amount of nodes in binary tree with height (h - 1)?

That's 2^0 + 2^1 + 2^2 + ... + 2^(h - 1).

> c) What is maximum amount of nodes of height (h) in binary tree and
> how it is related to answers to a) and to b)?

Hm. I think it must be (a) minus (b), that is

2^0 + 2^1 + 2^2 + ... + 2^h
- (2^0 + 2^1 + 2^2 + ... + 2^(h - 1)) = 2^h

> d) How can binary tree's size in nodes (n) limit answer to c)?

I can see it does limit. I'm not sure how it does it. If n is not the
maximum number of nodes, then the amount of nodes in a certain height k
will be less than 2^k.

> However if you can not answer these questions then the whole issue
> can be in no way explained to you because you don't know the
> basics.

Thank you for the insights you've given me.

Richard Heathfield

4/18/2016 8:46:00 PM

0

On 18/04/16 17:36, Daniel Bastos wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:
>
>> On 18/04/16 12:48, Daniel Bastos wrote:
>>> I wonder if anyone can show me intuitively that an n-element heap can
>>> have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
>>> any idea that help me see this. Thank you!
>>
>> The intuitive way to think about this is to recognise that a heap is
>> really a binary search tree in disguise, and shares many of the same
>> properties. A binary search tree of height h > 0 will have at most
>> 2^(h-1) nodes at its deepest level (and a perfectly-balanced,
>> perfectly-filled binary search tree will have exactly that many nodes
>> at that level).
>
> I'm unable to verify that a search tree of height h > 0 will have at
> most 2^(h-1) nodes at its deepest level. Should it be 2^h?

No.

> (My
> reasoning below.)
>
> --8<---------------cut here---------------start------------->8---
> A binary search tree of height 0 will have at most 2^0 nodes at its
> deepest level.

2^0 = 1.

A binary search tree of height 0 has no nodes, not one node.

> A binary search tree of height 1 will have at most 2^1 nodes at its
> deepest level.

2^1 = 2.

A binary search tree of height 1 has one node, not two.

1:.*

> A binary search tree of height 2 will have at most 2^2 nodes at its
> deepest level.

2^2 = 4.

A binary search tree of height 2 has three nodes, two of which are at
level 2:

1:..*
2: *.*

Let's show it for h = 4:

1:...........*...........
2:.....*...........*.....
3:..*.....*.....*.....*..
4:.*.*...*.*...*.*...*.*.

At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Ben Bacarisse

4/19/2016 12:56:00 AM

0

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 18/04/16 17:36, Daniel Bastos wrote:
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>
>>> On 18/04/16 12:48, Daniel Bastos wrote:
>>>> I wonder if anyone can show me intuitively that an n-element heap can
>>>> have at most ceil(n/2^{h + 1}) nodes of height h. I would appreciate
>>>> any idea that help me see this. Thank you!
>>>
>>> The intuitive way to think about this is to recognise that a heap is
>>> really a binary search tree in disguise, and shares many of the same
>>> properties. A binary search tree of height h > 0 will have at most
>>> 2^(h-1) nodes at its deepest level (and a perfectly-balanced,
>>> perfectly-filled binary search tree will have exactly that many nodes
>>> at that level).
>>
>> I'm unable to verify that a search tree of height h > 0 will have at
>> most 2^(h-1) nodes at its deepest level. Should it be 2^h?
>
> No.
>
>> (My
>> reasoning below.)
>>
>> --8<---------------cut here---------------start------------->8---
>> A binary search tree of height 0 will have at most 2^0 nodes at its
>> deepest level.
>
> 2^0 = 1.
>
> A binary search tree of height 0 has no nodes, not one node.
>
>> A binary search tree of height 1 will have at most 2^1 nodes at its
>> deepest level.
>
> 2^1 = 2.
>
> A binary search tree of height 1 has one node, not two.
>
> 1:.*
>
>> A binary search tree of height 2 will have at most 2^2 nodes at its
>> deepest level.
>
> 2^2 = 4.
>
> A binary search tree of height 2 has three nodes, two of which are at
> level 2:
>
> 1:..*
> 2: *.*

You are using a non-standard notion of height. The normal meaning is so
universal that I'd go so far as to say you are using an incorrect notion
of height. The height is (usually) measured by edges -- the depth of a
node being the number of edges in the path to the root and the height of
a tree being the maximum depth taken over all nodes.

> Let's show it for h = 4:
>
> 1:...........*...........
> 2:.....*...........*.....
> 3:..*.....*.....*.....*..
> 4:.*.*...*.*...*.*...*.*.
>
> At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.

Most people would call that a tree of height 3. I've never seen your
counting used for tree height, but I have led a sheltered life.

--
Ben.

Richard Heathfield

4/19/2016 1:05:00 AM

0

On 19/04/16 01:55, Ben Bacarisse wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:
>
<snip>
>
>> Let's show it for h = 4:
>>
>> 1:...........*...........
>> 2:.....*...........*.....
>> 3:..*.....*.....*.....*..
>> 4:.*.*...*.*...*.*...*.*.
>>
>> At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.
>
> Most people would call that a tree of height 3. I've never seen your
> counting used for tree height, but I have led a sheltered life.

One can envisage nodes in a tree as if they were rooms in a building,
and the height is the number of storeys. h=4

One can envisage nodes in a tree as if they were posts in a fence, and
the height is the number of fence-rails you need. h=3

Both make sense. I think my way makes more sense, but then I would,
wouldn't I?

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Ben Bacarisse

4/19/2016 1:28:00 AM

0

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 19/04/16 01:55, Ben Bacarisse wrote:
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>
> <snip>
>>
>>> Let's show it for h = 4:
>>>
>>> 1:...........*...........
>>> 2:.....*...........*.....
>>> 3:..*.....*.....*.....*..
>>> 4:.*.*...*.*...*.*...*.*.
>>>
>>> At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.
>>
>> Most people would call that a tree of height 3. I've never seen your
>> counting used for tree height, but I have led a sheltered life.
>
> One can envisage nodes in a tree as if they were rooms in a building,
> and the height is the number of storeys. h=4
>
> One can envisage nodes in a tree as if they were posts in a fence, and
> the height is the number of fence-rails you need. h=3

One could, but why would one? Why is that analogy better than others
where height is usually a measured length? Or, more exactly, given that
there is an established usage, are the benefits of your usage enough to
outweigh the resulting confusion? At the moment I see no advantages at
all.

Do you use the same counting for depth? Does the root have depth 1?

> Both make sense. I think my way makes more sense, but then I would,
> wouldn't I?

Starting out saying "no" is a bit strong then! Saying "There are two
ways to measure the height and I'm using the less usual one" wouldn't
have been so confrontational.

--
Ben.

Richard Heathfield

4/19/2016 1:30:00 AM

0

On 19/04/16 02:28, Ben Bacarisse wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:
>
>> On 19/04/16 01:55, Ben Bacarisse wrote:
>>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>>
>> <snip>
>>>
>>>> Let's show it for h = 4:
>>>>
>>>> 1:...........*...........
>>>> 2:.....*...........*.....
>>>> 3:..*.....*.....*.....*..
>>>> 4:.*.*...*.*...*.*...*.*.
>>>>
>>>> At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.
>>>
>>> Most people would call that a tree of height 3. I've never seen your
>>> counting used for tree height, but I have led a sheltered life.
>>
>> One can envisage nodes in a tree as if they were rooms in a building,
>> and the height is the number of storeys. h=4
>>
>> One can envisage nodes in a tree as if they were posts in a fence, and
>> the height is the number of fence-rails you need. h=3
>
> One could, but why would one? Why is that analogy better than others
> where height is usually a measured length?

You're assuming that I thought it all through, instead of shooting from
the hip. Why would you make that assumption?

<snip>

> Starting out saying "no" is a bit strong then! Saying "There are two
> ways to measure the height and I'm using the less usual one" wouldn't
> have been so confrontational.

If you're trying to make me feel guilty, you're succeeding. Please stop
it. :-)

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within