Number of heaps using n distinct integers- Time complexity

r.satish Srinivas Source

I am solving the problem to find the maximum number of max heaps that can be formed using n distinct integers (say 1..n). I have solved it using the following recurrence with some help from this: https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements : T(N) = N-1 (C) L * T(L) * T(R). where L is the number of nodes in the left subtree and R is the number of nodes in the right subtree. I have also implemented it in c++ using dynamic programming. But I am stuck in find the time complexity of it. Can someone help me with this?

#include <iostream>
using namespace std;

#define MAXN 105 //maximum value of n here

int dp[MAXN];  //dp[i] = number of max heaps for i distinct integers
int nck[MAXN][MAXN]; //nck[i][j] = number of ways to choose j elements form i elements, no order */
int log2[MAXN]; //log2[i] = floor of logarithm of base 2 of i

//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 intialize 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;
}
algorithmdata-structurestime-complexityheapdynamic-programming

Answers

comments powered by Disqus