All Questions
Tagged with heaps combinatorics
6 questions
1
vote
0
answers
30
views
How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?
The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion:
$$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
- 145
2
votes
2
answers
131
views
Number of possible heaps on $\{1,...,2^h-1\}$
Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.
Definition
A binary tree is ordered ...
- 145
1
vote
2
answers
2k
views
Number of possible min heaps
The number of possible min-heaps containing each value from {1, 2, 3,
4, 5, 6, 7} exactly once is --------------
According to me, the answer should be 48. The first element 1 is fixed as root. The ...
- 323
2
votes
1
answer
3k
views
The maximum number of nodes in a heap tree of degree d and depth k
The maximum number of nodes in a binary tree of depth k is defined by $2^{(k+1)}-1$, but the same rule doesn't appear to work for heap trees of different degrees.
Let's say I have the following tree ...
- 123
2
votes
1
answer
279
views
Using a binary heap to solve an equation
I have to find a solution for this equation:
I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n.
$a^5 + b^5 = c^5 + d ^ 5$
I first thought ...
- 141
23
votes
1
answer
10k
views
How many different max-heaps exist for a list of n integers?
How many different max-heaps exist for a list of $n$ integers?
Example: list [1, 2, 3, 4]
The max-heap can be either 4 3 2 1:
...
- 1,751