Minimum Cost of ropes-heaps

Given  n ropes of different lengths, we need to connect these ropes into one rope. We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until n ropes are connected into a single rope. Find the min possible cost required to connect all ropes.

Input: ropes = [8, 4, 6, 12]
Output: 58
Explanation: The optimal way to connect ropes is as follows
1. Connect the ropes of length 4 and 6 (cost is 10). Ropes after connecting: [8, 10, 12]
2. Connect the ropes of length 8 and 10 (cost is 18). Ropes after connecting: [18, 12]
3. Connect the ropes of length 18 and 12 (cost is 30).
Total cost to connect the ropes is 10 + 18 + 30 = 58

we will solve this question using heap(priority queue):

Algorithm: 

1. we will use a min-heap and insert all lengths into the min-heap.
2. now as the lowest element is on the top of the heap , run a while loop till there are atleast two elements in heap, now
   
   1. Extract the minimum and second minimum from min-heap
   2. Add the above two extracted values and insert the added value back to the min-heap.
   3. lets maintain a variable for total cost and keep incrementing it by the sum of extracted values.
3. Return the value of this total cost.

code :

c++ implementation.

   
int minCost(int arr[], int n) {
    
    # creating a min heap using priority queue and adding all array elements to it
   priority_queue< int, vector<int>, greater<int> > q(arr,arr+n);
   
   int result=0;       # variable to maintain total cost
   
   while(!q.empty() && q.size()>1) 
   {
       int x= q.top();
       q.pop();
       
       int y =q.top();
       q.pop();
       
       int s=x+y;
       
       q.push(s);
       result=result+s;
       
   }
   return result;
   
}

Complexity Analysis:

• Time Complexity: O(nLogn)
• Auxiliary Complexity: O(n). 
  
  

we can use long long datatype instead of int datatype if input elements are very large:

   
long long minCost(long long arr[], long long n) {
    
   priority_queue< long long, vector<long long>, greater<long long> > q(arr,arr+n);
   long long result=0;
   while(!q.empty() && q.size()>1)
   {
       long long x= q.top();
       q.pop();
       
       long long y =q.top();
       q.pop();
       
       long long s=x+y;
       q.push(s);
       result=result+s;
       
   }
   return result;
   
}