# Distinct Binary Heaps

I have $$n$$ elements out of $$n-1$$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it.

My analysis : I started with $$n$$ distinct elements. Since root is fixed( maximum element) we can choose $$l$$(found using deducting total elements from elements in penultimate level) from remaining $$n-1$$ elements and recursively choose for Left Sub-tree and Right Sub-tree.

Recurrence Relation :

$$T(n)={n-1 \choose l} * T(l) * T(r)$$

Now for $$n-1$$ distinct elements(given), for root we have $$2$$ options i.e. maximum elements and we can recurse as above for left and right sub-tree. But since the repeated element is also there I am not able to figure out exact way to do so.

Eg: $$A=[2,6,6] =>$$ There are 2 distinct max heaps $$=> [6,2,6] , [6,6,2]$$

I am unable to think of the way to find out the number of max heaps in this case. Can someone think of algorithm/recurrence relation to find so ?

• Why is there 2 distinct heap for [2,6,6]? Max heap is [6,2,6] and [6,6,2] while min heap is [2, 6, 6] and the answer should be 3? – Christopher Boo Sep 18 '19 at 10:41
• @ChristopherBoo Sorry, I forgot to mention we can make max heaps only. I edited the question for clarity. – tanmay_freak Sep 18 '19 at 22:54

If the duplicate element is the maximum element, the answer is the same as when all numbers are distinct. Let's say the duplicate element is $$a_1, a_2$$. Even though they are the same, we can treat it as $$a_1 > a_2$$, and then remove the duplicate heaps where the only difference is the exchange of $$a_1, a_2$$, but that is not possible because $$a_1$$ is always at the root. So no duplicates found.

If the duplicate element is the minimum element, the problem gets more interesting. Let $$S(n)$$ be the number of max heaps such that the minimum element is duplicated, and $$T(n)$$ be the number of max heaps such that there are no duplicates. We already know that

$$T(n) = {{n-1}\choose {l}} \times T(l) \times T(r)$$

with base case $$T(1) = 1$$.

For the duplicate case, we have 3 cases. We can put them both into the left subtree, both into the right subtree, or one in each subtree. Hence, the recursion is

$$S(n) = {{n-3}\choose {l-2}} S(l) T(r) + {{n-3}\choose {r-2}} T(l) S(r) + {{n-3}\choose {l-1}} T(l) T(r)$$

with base case $$S(1) = 0, S(2) = 1, S(3) = 1$$.

• Thanks I got it now. Also in the duplicate case, is the finding the value of $l,r$ for $S(l),S(r)$ same as finding the value of $l,r$ for $T(l),T(r)$. If not so, could you elaborate on it a little bit ? – tanmay_freak Sep 19 '19 at 17:27
• I believe it is the same. The size of the left/right heap shouldn't change just because there's a duplicate. Also, if it helped you, can you mark my answer as accepted :P – Christopher Boo Sep 20 '19 at 1:58
• Yes it did. Thank you ! – tanmay_freak Sep 20 '19 at 6:05