# Prove number of nodes in heap

Consider a variation of the normal heap which we will call the x-heap

The x-heap of height $$h$$ has the following properties:

• It will have $$2^h$$ nodes

• A height of $$0$$ corresponds to the single root node

• The format of the tree is a root with exactly one child, which in turn is the root of a complete binary tree

We define a collection of x-heaps to be sequence $$X_0, X_1,\dots,X_k$$ with the following properties:

• $$height(X_{i-1})\leq height(X_i)$$, where $$0\leq i \leq k$$

• There exist at least $$i + 1$$ (X-heaps) of $$height \leq i$$, where $$0\leq i \leq k$$

• There exist at most $$i + 2$$ (X-heaps) of $$height \leq i$$, where $$0\leq i \leq k$$

We cannot have a collection with all of the same type of x-heap (can't have collection with all single nodes)

Prove that if $$X_0,X_1,\dots,X_k$$ is a collection, then the total number of nodes is between $$2^k$$ and $$2^{k+1}$$

I am not sure where to start here. I feel I must use the last two bullet points, but not sure how.

Moreover, the trees in a collection can have height $$1, 3, 4, 8$$ as an example. It is not limited to increasing by $$1$$.

Interesting proposition.

Moreover, the trees in a collection can have height 1,3,4,8 as an example. It is not limited to increasing by 1.

How could 1,3,4,8 be an example? If you set $$i=0$$ in "there exist at least $$i + 1$$ x-heaps of $$height \leq i$$, where $$0\leq i \leq k$$", you know there exist at least 1 X-heap of height less than or equal to 0. That means $$X_0$$ must be 0. In fact, the height will be increased by 0 or 1 every time.

## Reformulation

Since an x-heap is completely determined by its height, let us introduce almost-natural sequences, which comes from a collection of x-heaps in the question.

An almost-natural sequence is a non-decreasing sequence of integers $$0=h_0, h_1,\dots,h_k$$, where $$k\ge0$$, such that, for all $$0\le i\le h_k$$,

• at least $$i + 1$$ of them are not greater than $$i$$
• at most $$i + 2$$ of them are not greater than $$i$$.

Characterization of almost-natural sequences. An almost-natural sequence must be one of the following.

• $$0, 1, \cdots, k-1, k$$, i.e., the first $$k+1$$ natural numbers.
• $$0, 1, \cdots, m-1, m, m, m+1, \cdots, k-2, k-1$$, i.e., the first $$k$$ natural numbers with one of them, $$m$$ repeated once, where $$0\le m\le k-1$$.

Corollary. $$2^k\le\sum_{i=0}^k2^{h_k}\le2^{k+1}-1$$ for an almost-natural sequence $$h_0,h_1,\dots,h_k$$.

## Exercises

Here are a few related exercises.

Exercise 1. Prove the characterization of almost-natural sequences.

Here is a hint. Does a given almost-natural sequence contain a repeated number? If yes, prove that number appears exactly twice and no other number is repeated.

Exercise 2. Prove the corollary.

Exercise 3. Let a d-natural sequence be a non-decreasing sequence of $$k+1$$ integers $$0=h_0, h_1,\dots,h_k$$ such that at least $$i+1$$ and at most $$i+1+d$$ of them are not greater than $$i$$ for all $$0\le i\le h_k$$. Determine the lower bound and upper bound of $$\sum_{i=0}^k{h_k}$$ and $$\sum_{i=0}^k2^{h_k}\,.$$

• Sorry, an error in my question. We start counting at $0$, so two heaps (of height 0 and 1) actually has m= $1$, thus $2^1 \leq 3 \leq 2^2$ holds. I need help proving this – VD18421 Feb 10 at 14:39
• Please use my hint to exercise 1. – Apass.Jack Feb 10 at 16:20
• Does the hint work for you? – Apass.Jack Feb 12 at 3:22
• Yes the "characterization" helps me. Thanks! – VD18421 Feb 12 at 19:27