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

Groups > comp.programming > #6512

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

Show key headers only | View raw

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.

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