Number of ways to form a heap with n distinct integers

22 August 2024

0

Given n, how many distinct Max Heap can be made from n distinct integers?

Examples:

Input : n = 3
Output : Assume the integers are 1, 2, 3.
Then the 2 possible max heaps are:       
            3
           / \
          1   2

           3
          / \
         2   1

Input : n = 4
Output : Assume the integers are 1, 2, 3, 4.
Then the 3 possible max heaps are:
        4 
       / \ 
      3   2 
     / 
    1

        4 
       / \ 
      2   3 
     / 
    1

        4 
       / \ 
      3   1 
     / 
    2

Since there is only one element as the root, it must be the largest number. Now we have n-1 remaining elements. The main observation here is that because of the max heap properties, the structure of the heap nodes will remain the same in all instances, but only the values in the nodes will change.

Assume there are l elements in the left sub-tree and r elements in the right sub-tree. Now for the root, l + r = n-1. From this we can see that we can choose any l of the remaining n-1 elements for the left sub-tree as they are all smaller than the root.

We know the there are $\binom{n-1}{l}$ ways to do this. Next for each instance of these, we can have many heaps with l elements and for each of those we can have many heaps with r elements. Thus we can consider them as subproblems and recur for the final answer as:
T(n) = $\binom{n-1}{l}$ * T(L) * T(R).

Now we have to find the values for l and r for a given n. We know that the height of the heap h = $\log_2 n$ . Also the maximum number of elements that can be present in the h th level of any heap, m = $2^h$ , where the root is at the 0th level. Moreover the number of elements actually present in the last level of the heap p = n – ( $2^h$ – 1). (since $2^h - 1$ number of nodes present till the penultimate level). Thus, there can be two cases: when the last level is more than or equal to half-filled:
l = $2^h$ – 1, if p >= m / 2

(or) the last level is less than half-filled:
l = $2^h$ – 1 – ((m / 2) – p), if p < m / 2
(we get $2^h$ – 1 here because left subtree has $2^0 + 2^1 +..+2^{h-1}$ nodes.
From this we can also say that r = n – l – 1.

We can use the dynamic programming approach discussed in this post here to find the values of $\binom{n}{k}$ . Similarly if we look at the recursion tree for the optimal substructure recurrence formed above, we can see that it also has overlapping subproblems property, hence can be solved using dynamic programming:

             T(7)
            /    \
          T(3)   T(3)
         /  \     /  \    
     T(1)  T(1) T(1) T(1)

Following is the implementation of the above approach:

C++

// CPP program to count max heaps with n distinct keys
#include <iostream>
using namespace std;
 
#define MAXN 105 // maximum value of n here
 
// dp[i] = number of max heaps for i distinct integers
int dp[MAXN]; 
 
// nck[i][j] = number of ways to choose j elements
//             form i elements, no order */
int nck[MAXN][MAXN]; 
 
// log2[i] = floor of logarithm of base 2 of i
int log2[MAXN]; 
 
// to calculate nCk
int choose(int n, int k)
{
    if (k > n)
        return 0;
    if (n <= 1)
        return 1;
    if (k == 0)
        return 1;
 
    if (nck[n][k] != -1)
        return nck[n][k];
 
    int answer = choose(n - 1, k - 1) + choose(n - 1, k);
    nck[n][k] = answer;
    return answer;
}
 
// calculate l for give value of n
int getLeft(int n)
{
    if (n == 1)
        return 0;
 
    int h = log2[n];
 
    // max number of elements that can be present in the 
    // hth level of any heap
    int numh = (1 << h); //(2 ^ h)
 
    // number of elements that are actually present in
    // last level(hth level)
    // (2^h - 1)
    int last = n - ((1 << h) - 1);
 
    // if more than half-filled
    if (last >= (numh / 2))
        return (1 << h) - 1; // (2^h) - 1
    else
        return (1 << h) - 1 - ((numh / 2) - last);
}
 
// find maximum number of heaps for n
int numberOfHeaps(int n)
{
    if (n <= 1)
        return 1;
 
    if (dp[n] != -1)
        return dp[n];
 
    int left = getLeft(n);
    int ans = (choose(n - 1, left) * numberOfHeaps(left)) * 
                             (numberOfHeaps(n - 1 - left));
    dp[n] = ans;
    return ans;
}
 
// function to initialize arrays
int solve(int n)
{
    for (int i = 0; i <= n; i++)
        dp[i] = -1;
 
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            nck[i][j] = -1;
 
    int currLog2 = -1;
    int currPower2 = 1;
 
    // for each power of two find logarithm
    for (int i = 1; i <= n; i++) {
        if (currPower2 == i) {
            currLog2++;
            currPower2 *= 2;
        }
        log2[i] = currLog2;
    }
 
    return numberOfHeaps(n);
}
 
// driver function
int main()
{
    int n = 10;
    cout << solve(n) << endl;
    return 0;
}

Java

// Java program to count max heaps with n distinct keys 
import java.util.*;
import java.io.*;
 
class GFG
{
 
    static int MAXN = 105; // maximum value of n here 
 
    // dp[i] = number of max heaps for i distinct integers 
    static int[] dp = new int[MAXN];
 
    // nck[i][j] = number of ways to choose j elements 
    //         form i elements, no order */ 
    static int[][] nck = new int[MAXN][MAXN];
 
    // log2[i] = floor of logarithm of base 2 of i 
    static int[] log2 = new int[MAXN];
 
    // to calculate nCk 
    public static int choose(int n, int k) 
    {
        if (k > n) 
        {
            return 0;
        }
        if (n <= 1) 
        {
            return 1;
        }
        if (k == 0)
        {
            return 1;
        }
 
        if (nck[n][k] != -1)
        {
            return nck[n][k];
        }
 
        int answer = choose(n - 1, k - 1) + choose(n - 1, k);
        nck[n][k] = answer;
        return answer;
    }
 
    // calculate l for give value of n 
    public static int getLeft(int n) 
    {
        if (n == 1) 
        {
            return 0;
        }
 
        int h = log2[n];
 
        // max number of elements that can be present in the 
        // hth level of any heap 
        int numh = (1 << h); //(2 ^ h) 
 
        // number of elements that are actually present in 
        // last level(hth level) 
        // (2^h - 1) 
        int last = n - ((1 << h) - 1);
 
        // if more than half-filled 
        if (last >= (numh / 2))
        {
            return (1 << h) - 1; // (2^h) - 1 
        } 
        else
        {
            return (1 << h) - 1 - ((numh / 2) - last);
        }
    }
 
    // find maximum number of heaps for n 
    public static int numberOfHeaps(int n) 
    {
        if (n <= 1)
        {
            return 1;
        }
 
        if (dp[n] != -1) 
        {
            return dp[n];
        }
 
        int left = getLeft(n);
        int ans = (choose(n - 1, left) * numberOfHeaps(left))
                * (numberOfHeaps(n - 1 - left));
        dp[n] = ans;
        return ans;
    }
 
    // function to initialize arrays 
    public static int solve(int n)
    {
        for (int i = 0; i <= n; i++)
        {
            dp[i] = -1;
        }
 
        for (int i = 0; i <= n; i++) 
        {
            for (int j = 0; j <= n; j++)
            {
                nck[i][j] = -1;
            }
        }
 
        int currLog2 = -1;
        int currPower2 = 1;
 
        // for each power of two find logarithm 
        for (int i = 1; i <= n; i++) 
        {
            if (currPower2 == i) 
            {
                currLog2++;
                currPower2 *= 2;
            }
            log2[i] = currLog2;
        }
 
        return numberOfHeaps(n);
    }
 
    // Driver code 
    public static void main(String[] args) 
    {
        int n = 10;
        System.out.print(solve(n));
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python program to count max heaps with n distinct keys
 
MAXN = 105 # maximum value of n here
 
# dp[i] = number of max heaps for i distinct integers
dp = [0]*MAXN
 
# nck[i][j] = number of ways to choose j elements
#             form i elements, no order */
nck = [[0 for i in range(MAXN)] for j in range(MAXN)]
 
# log2[i] = floor of logarithm of base 2 of i
log2 = [0]*MAXN
 
# to calculate nCk
def choose(n, k):
    if (k > n):
        return 0
    if (n <= 1):
        return 1
    if (k == 0):
        return 1
 
    if (nck[n][k] != -1):
        return nck[n][k]
 
    answer = choose(n - 1, k - 1) + choose(n - 1, k)
    nck[n][k] = answer
    return answer
 
 
# calculate l for give value of n
def getLeft(n):
    if (n == 1):
        return 0
 
    h = log2[n]
 
    # max number of elements that can be present in the 
    # hth level of any heap
    numh = (1 << h) #(2 ^ h)
 
    # number of elements that are actually present in
    # last level(hth level)
    # (2^h - 1)
    last = n - ((1 << h) - 1)
 
    # if more than half-filled
    if (last >= (numh // 2)):
        return (1 << h) - 1 # (2^h) - 1
    else:
        return (1 << h) - 1 - ((numh // 2) - last)
 
 
# find maximum number of heaps for n
def numberOfHeaps(n):
    if (n <= 1):
        return 1
 
    if (dp[n] != -1):
        return dp[n]
 
    left = getLeft(n)
    ans = (choose(n - 1, left) * numberOfHeaps(left)) * (numberOfHeaps(n - 1 - left))
    dp[n] = ans
    return ans
 
 
# function to initialize arrays
def solve(n):
    for i in range(n+1):
        dp[i] = -1
 
    for i in range(n+1):
        for j in range(n+1):
            nck[i][j] = -1
 
    currLog2 = -1
    currPower2 = 1
 
    # for each power of two find logarithm
    for i in range(1,n+1):
        if (currPower2 == i):
            currLog2 += 1
            currPower2 *= 2
        log2[i] = currLog2
    return numberOfHeaps(n)
 
 
# Driver code
n = 10
print(solve(n))
 
# This code is contributed by ankush_953

C#

// C# program to count max heaps with n distinct keys 
using System; 
   
class GFG 
{ 
    static int MAXN = 105; // maximum value of n here 
       
    // dp[i] = number of max heaps for i distinct integers 
    static int[] dp = new int[MAXN];  
       
    // nck[i][j] = number of ways to choose j elements 
    //             form i elements, no order */ 
    static int[,] nck = new int[MAXN,MAXN];  
       
    // log2[i] = floor of logarithm of base 2 of i 
    static int[] log2 = new int[MAXN];  
       
    // to calculate nCk 
    public static int choose(int n, int k) 
    { 
        if (k > n) 
            return 0; 
        if (n <= 1) 
            return 1; 
        if (k == 0) 
            return 1; 
       
        if (nck[n,k] != -1) 
            return nck[n,k]; 
       
        int answer = choose(n - 1, k - 1) + choose(n - 1, k); 
        nck[n,k] = answer; 
        return answer; 
    } 
       
    // calculate l for give value of n 
    public static int getLeft(int n) 
    { 
        if (n == 1) 
            return 0; 
       
        int h = log2[n]; 
       
        // max number of elements that can be present in the  
        // hth level of any heap 
        int numh = (1 << h); //(2 ^ h) 
       
        // number of elements that are actually present in 
        // last level(hth level) 
        // (2^h - 1) 
        int last = n - ((1 << h) - 1); 
       
        // if more than half-filled 
        if (last >= (numh / 2)) 
            return (1 << h) - 1; // (2^h) - 1 
        else
            return (1 << h) - 1 - ((numh / 2) - last); 
    } 
       
    // find maximum number of heaps for n 
    public static int numberOfHeaps(int n) 
    { 
        if (n <= 1) 
            return 1; 
       
        if (dp[n] != -1) 
            return dp[n]; 
       
        int left = getLeft(n); 
        int ans = (choose(n - 1, left) * numberOfHeaps(left)) *  
                                 (numberOfHeaps(n - 1 - left)); 
        dp[n] = ans; 
        return ans; 
    } 
       
    // function to initialize arrays 
    public static int solve(int n) 
    { 
        for (int i = 0; i <= n; i++) 
            dp[i] = -1; 
       
        for (int i = 0; i <= n; i++) 
            for (int j = 0; j <= n; j++) 
                nck[i,j] = -1; 
       
        int currLog2 = -1; 
        int currPower2 = 1; 
       
        // for each power of two find logarithm 
        for (int i = 1; i <= n; i++) { 
            if (currPower2 == i) { 
                currLog2++; 
                currPower2 *= 2; 
            } 
            log2[i] = currLog2; 
        } 
       
        return numberOfHeaps(n); 
    } 
       
    // driver function 
    static void Main() 
    { 
        int n = 10; 
        Console.Write(solve(n)); 
    }
    //This code is contributed by DrRoot_
}

Javascript

<script>
 
// JavaScript program to count max heaps with n distinct keys 
 
let MAXN = 105; // maximum value of n here 
 
// dp[i] = number of max heaps for i distinct integers 
let dp = new Array(MAXN);
 
// nck[i][j] = number of ways to choose j elements 
    //         form i elements, no order */
let nck = new Array(MAXN);
for(let i=0;i<MAXN;i++)
{
    nck[i]=new Array(MAXN);
    for(let j=0;j<MAXN;j++)
        nck[i][j]=0;
}
 
// log2[i] = floor of logarithm of base 2 of i 
let log2 = new Array(MAXN);
 
 // to calculate nCk 
function choose(n,k)
{
    if (k > n) 
        {
            return 0;
        }
        if (n <= 1) 
        {
            return 1;
        }
        if (k == 0)
        {
            return 1;
        }
   
        if (nck[n][k] != -1)
        {
            return nck[n][k];
        }
   
        let answer = choose(n - 1, k - 1) + choose(n - 1, k);
        nck[n][k] = answer;
        return answer;
}
 
 // calculate l for give value of n
function getLeft(n)
{
    if (n == 1) 
        {
            return 0;
        }
   
        let h = log2[n];
   
        // max number of elements that can be present in the 
        // hth level of any heap 
        let numh = (1 << h); //(2 ^ h) 
   
        // number of elements that are actually present in 
        // last level(hth level) 
        // (2^h - 1) 
        let last = n - ((1 << h) - 1);
   
        // if more than half-filled 
        if (last >= (numh / 2))
        {
            return (1 << h) - 1; // (2^h) - 1 
        } 
        else
        {
            return (1 << h) - 1 - ((numh / 2) - last);
        }
}
 
// find maximum number of heaps for n 
function numberOfHeaps(n)
{
    if (n <= 1)
        {
            return 1;
        }
   
        if (dp[n] != -1) 
        {
            return dp[n];
        }
   
        let left = getLeft(n);
        let ans = (choose(n - 1, left) * numberOfHeaps(left))
                * (numberOfHeaps(n - 1 - left));
        dp[n] = ans;
        return ans;
}
 
// function to initialize arrays 
function solve(n)
{
    for (let i = 0; i <= n; i++)
        {
            dp[i] = -1;
        }
   
        for (let i = 0; i <= n; i++) 
        {
            for (let j = 0; j <= n; j++)
            {
                nck[i][j] = -1;
            }
        }
   
        let currLog2 = -1;
        let currPower2 = 1;
   
        // for each power of two find logarithm 
        for (let i = 1; i <= n; i++) 
        {
            if (currPower2 == i) 
            {
                currLog2++;
                currPower2 *= 2;
            }
            log2[i] = currLog2;
        }
   
        return numberOfHeaps(n);
}
 
// Driver code 
let n = 10;
document.write(solve(n));
 
// This code is contributed by rag2127
 
</script>

Output

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Number of ways to form a heap with n distinct integers

C++

Java

Python3

C#

Javascript

Java Program for Longest Common Subsequence

Maximum height of Tree when any Node can be considered as Root

Print Fibonacci sequence using 2 variables

LEAVE A REPLY Cancel reply

Most Popular

One UI 7: Everything you need to know

Review: The Ulefone Armor Mini 20T Pro makes other rugged phones seem flimsy

Best midrange Android phones in 2024

I tried a Xiaomi mid-ranger for the first time in years, and I’m glad the Pixel 8a exists in the US

Recent Comments

EDITOR PICKS

One UI 7: Everything you need to know

Review: The Ulefone Armor Mini 20T Pro makes other rugged phones seem flimsy

Best midrange Android phones in 2024

POPULAR POSTS

One UI 7: Everything you need to know

Review: The Ulefone Armor Mini 20T Pro makes other rugged phones seem flimsy

Best midrange Android phones in 2024

POPULAR CATEGORY

ABOUT US

FOLLOW US