Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #6507
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: on an n-element heap and its nodes of height h |
| Date | 2016-04-18 14:41 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <nf2o0k$gcv$1@dont-email.me> (permalink) |
| References | <86h9ez2l43.fsf@toledo.com> |
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
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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