Connect n ropes with minimum cost - GeeksforGeeks

Connect n ropes with minimum cost - GeeksforGeeks
There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

the lengths of the ropes which are picked first are included more than once in total cost. Therefore, the idea is to connect smallest two ropes first and recur for remaining ropes. This approach is similar to Huffman Coding. We put smallest ropes down the tree so that they can be repeated multiple times rather than the longer ropes.

int minCost(int arr[], int n)

{

    // Create a priority queue ( http://www.cplusplus.com/reference/queue/priority_queue/ )

    // By default 'less' is used which is for decreasing order

    // and 'greater' is used for increasing order

    priority_queue< int, vector<int>, greater<int> > pq(arr, arr+n);

    // Initialize result

    int res = 0;

    // While size of priority queue is more than 1

    while (pq.size() > 1)

    {

        // Extract shortest two ropes from pq

        int first = pq.top();

        pq.pop();

        int second = pq.top();

        pq.pop();

        // Connect the ropes: update result and

        // insert the new rope to pq

        res += first + second;

        pq.push(first + second);

    }

    return res;

}

Read full article from Connect n ropes with minimum cost - GeeksforGeeks