Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on an n-element heap and its nodes of height h Date: Mon, 18 Apr 2016 13:36:42 -0300 Organization: Aioe.org NNTP Server Lines: 41 Message-ID: <864may3mcl.fsf@toledo.com> References: <86h9ez2l43.fsf@toledo.com> NNTP-Posting-Host: 2qgpAfNKKNVFtQ8BuAGQfg.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:SKHPzcTcUlXFab+Lpp52MlC9mxc= Xref: csiph.com comp.programming:6512 Richard Heathfield 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.