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:56:28 -0300 Organization: Aioe.org NNTP Server Lines: 43 Message-ID: <86potm26v7.fsf@toledo.com> References: <86h9ez2l43.fsf@toledo.com> <0e51d33e-14d5-44c4-a9f6-fd8af6b74bf8@googlegroups.com> NNTP-Posting-Host: 2qgpAfNKKNVFtQ8BuAGQfg.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) Cancel-Lock: sha1:F7MHfGGxmI2fJSK9A/2PQQm5H98= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:6514 Öö Tiib 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.