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

Groups > comp.programming > #6514

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

Show key headers only | View raw

Öö 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.

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