2
$\begingroup$

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

enter image description here

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$.

$\endgroup$
0
$\begingroup$

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}\,.$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – VD18421 Feb 10 at 14:39
  • $\begingroup$ Please use my hint to exercise 1. $\endgroup$ – Apass.Jack Feb 10 at 16:20
  • $\begingroup$ Does the hint work for you? $\endgroup$ – Apass.Jack Feb 12 at 3:22
  • $\begingroup$ Yes the "characterization" helps me. Thanks! $\endgroup$ – VD18421 Feb 12 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.