3
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Christopher Boo Sep 18 at 10:41
  • $\begingroup$ @ChristopherBoo Sorry, I forgot to mention we can make max heaps only. I edited the question for clarity. $\endgroup$ – tanmay_freak Sep 18 at 22:54
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – tanmay_freak Sep 19 at 17:27
  • $\begingroup$ 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 $\endgroup$ – Christopher Boo Sep 20 at 1:58
  • $\begingroup$ Yes it did. Thank you ! $\endgroup$ – tanmay_freak Sep 20 at 6:05

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.