geeksforgeeks:Connect n ropes with minimum cost

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.

For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.

Total cost for connecting all ropes is 5 + 9 + 15 = 29. This is the optimized cost for connecting ropes. Other ways of connecting ropes would always have same or more cost. For example, if we connect 4 and 6 first (we get three strings of 3, 2 and 10), then connect 10 and 3 (we get two strings of 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38.

Solution:

we notices that the length of the rope which are picked first are included more than once in total cost. Therefore the idea is to collect smallest two rope first and recur for the remaining ropes. it's similar with Huffman tree, we put the smallest ropes down the tree so that they can be repeated multiple times rather than the longest ropes.

1) create a MinHeap and insert all lengths into the min heap.

2) when there are more than one ropes in MinHeap, do the while.

1) get the first minimum and the second minimum in MinHeap

2) get the sum of the above two ropes and add the sum back into MinHeap

3) Maintain a variable cost for total cost

 public class MinHeap{
  public MinHeap(int[] len, int capacity) {
   capacity = capacity;
   arr = new int[capacity];
   for(int i = 0; i < len.length; i++) {
    this.heapInsert(len[i]);
   }
  }
  int size = 0;
  int[] arr;
  int capacity;
  public void heapInsert(int val) {
   arr[size] = val;
   int i = size;
   int parent = (i - 1)/2;
   while(i > 0 && arr[i] < arr[parent]) {
    swap(arr,i,parent);
    i = parent;
   }
   size++;
  }
  
  public void heapify(int i, int val) {
   arr[i] = val;
   int left = i * 2 + 1;
   int right = i * 2 + 2;
   while(left < size) {
    int min = i;
 
    if(arr[left] < arr[i]) {
     min = left;
    }
    if(right < size && arr[right] < arr[i]) {
     min = right;
    }
    if(min != i) {
     swap(arr,min,i);
    }
    i = min;
    left = i * 2 + 1;
    right = i * 2 + 2;
   }
  }
  
  public int getMin() {
   if(size ==0) {
    return Integer.MAX_VALUE;
   }
   int res = arr[0];
   if(size == 1) {
    size--;
    return res;
   }
   arr[0] = arr[size-1];
   size--;
   this.heapify(0, arr[0]);
   return res;
  }
  
  public void swap(int[] arr, int i, int j) {
   int temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 public int minCost(int[] len) {
  int cost = 0;
  int n = len.length;
  MinHeap heap = new MinHeap(len,n);
  while(heap.size != 1) {
   int rope1 = heap.getMin();
   int rope2 = heap.getMin();
   int sum = rope1 + rope2;
   cost = sum + cost;
   heap.heapInsert(cost);
  }
  cost = cost + heap.getMin();
  return cost;
 }