Heap: Connect ropes with minimum cost

Problem Statement:

You are given n ropes of different lengths.
You need to connect the ropes into one rope.
The cost to connect 2 ropes is equal to the sum of their lengths.
You need to connect the rpoes with minimum cost.

Example

Input: 4, 3, 2, 6.

If you connect the ropes in below order, you will get the optimal solution.
1. Connect 2 and 3. We have 4, 6, 5.

2. Connect 4 and 5. We have 6 and 9.

3. Connect 6 and 9.

Total cost = 5 + 9 + 15 = 29

Anyother way to connect will result in more cost.

Solution

The solution is very simple. We wil use min-heap.

We first enter all the elements into min heap.

Then we extract 2 values, we get first and second min, add them and them into min-heap.

Continue the same and return the total cost.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 

using namespace std;


 
int get_min_cost(int arr[], int n)
{

    priority_queue<int, vector<int>, greater<int> > pq(arr, arr + n);
 
    int res = 0;
 
    while (pq.size() > 1) 
    {
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
 
        res += first + second;
        pq.push(first + second);
    }
 
    return res;
}
 
int main()
{
    int arr[] = { 4, 3, 2, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Cost for connecting ropes is " << get_min_cost(arr, size)<<endl;
    return 0;
}

Output:

Cost for connecting ropes is 29