Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6519

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

Show all headers | View raw

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

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on an n-element heap and its nodes of height h Daniel Bastos <dbastos@toledo.com> - 2016-04-18 08:48 -0300
  Re: on an n-element heap and its nodes of height h Wally W. <ww84wa@aim.com> - 2016-04-18 08:08 -0400
  Re: on an n-element heap and its nodes of height h Öö Tiib <ootiib@hot.ee> - 2016-04-18 05:47 -0700
    Re: on an n-element heap and its nodes of height h Daniel Bastos <dbastos@toledo.com> - 2016-04-18 13:56 -0300
  Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-18 14:41 +0100
    Re: on an n-element heap and its nodes of height h Daniel Bastos <dbastos@toledo.com> - 2016-04-18 13:36 -0300
      Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-18 21:45 +0100
        Re: on an n-element heap and its nodes of height h Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-19 01:55 +0100
          Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-19 02:05 +0100
            Re: on an n-element heap and its nodes of height h Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-19 02:28 +0100
              Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-19 02:30 +0100
                Re: on an n-element heap and its nodes of height h Philip Lantz <prl@canterey.us> - 2016-04-18 21:24 -0700
                Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-19 09:23 +0100
                Re: on an n-element heap and its nodes of height h Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-20 11:01 +0100

csiph-web