0
$\begingroup$

The number of possible min-heaps containing each value from {1,2,3,4,5,6,7} exactly once is:

My approach went like this: fixing 1 in the root for the remaining 6 elements we can choose 3 of them and then make a full node(node with two children). For a given set of 3 nodes we can arrange them in 2! ways i.e the children can be altered and the parent node is fixed. The parent node is the smallest of the three nodes which are fixed and this can be repeated even for the right child of the root as well and the right child and the left child can be again permuted in 2! ways. This will ultimately give me $6C3*2!*2!$ which is 80.

Can anyone suggest to me a generic method which works for any set of given numbers?

$\endgroup$
  • $\begingroup$ You mean larger sets of the form $\{1,2\dots,2^n-1\}$, or do you mean sets with duplicates allowed? For the version without duplicates you are doing fine (fix minimum as root, divide in two parts & recurse). As far as I could see this is the approach listed at the Online Encyclopedia of Integer Sequences A056971: Number of (binary) heaps on n elements. $\endgroup$ – Hendrik Jan Mar 11 '18 at 1:44
  • $\begingroup$ @Hendrik Jan what I mean is ,is there a method by which we can solve this problem for any given number of input elements for example after removing the root if we are left with an odd number of elements then my approach needs to be changed because heaps are almost complete binary trees and we need to fill the leaves from the left most end then how do we check that ? $\endgroup$ – venkat Mar 11 '18 at 10:57

Your Answer

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

Browse other questions tagged or ask your own question.