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

Groups > comp.programming > #6520

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

Show all headers | View raw

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 18/04/16 17:36, Daniel Bastos wrote:
>> 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?
>
> No.
>
>> (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.
>
> 2^0 = 1.
>
> A binary search tree of height 0 has no nodes, not one node.
>
>> A binary search tree of height 1 will have at most 2^1 nodes at its
>> deepest level.
>
> 2^1 = 2.
>
> A binary search tree of height 1 has one node, not two.
>
> 1:.*
>
>> A binary search tree of height 2 will have at most 2^2 nodes at its
>> deepest level.
>
> 2^2 = 4.
>
> A binary search tree of height 2 has three nodes, two of which are at
> level 2:
>
> 1:..*
> 2: *.*

You are using a non-standard notion of height.  The normal meaning is so
universal that I'd go so far as to say you are using an incorrect notion
of height.  The height is (usually) measured by edges -- the depth of a
node being the number of edges in the path to the root and the height of
a tree being the maximum depth taken over all nodes.

> Let's show it for h = 4:
>
> 1:...........*...........
> 2:.....*...........*.....
> 3:..*.....*.....*.....*..
> 4:.*.*...*.*...*.*...*.*.
>
> At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.

Most people would call that a tree of height 3.  I've never seen your
counting used for tree height, but I have led a sheltered life.

-- 
Ben.

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