Connect n ropes with minimum cost | A class for Min Heap ; Array of elements in heap ; Current number of elements in min heap ; maximum possible size of min heap ; Constructor : Builds a heap from a given array a [ ] of given size ; A recursive method to heapify a subtree with the root at given index This method assumes that the subtrees are already heapified ; to get index of left child of node at index i ; to get index of right child of node at index i ; Method to remove minimum element ( or root ) from min heap ; Store the minimum value , and remove it from heap ; Inserts a new key ' k ' ; First insert the new key at the end ; Fix the min heap property if it is violated ; A utility function to check if size of heap is 1 or not ; A utility function to swap two elements ; The main function that returns the minimum cost to connect n ropes of lengths stored in len [ 0. . n - 1 ] ; Initialize result ; Create a min heap of capacity equal to n and put all ropes in it ; Iterate while size of heap doesn 't become 1 ; Extract two minimum length ropes from min heap ; Update total cost ; Insert a new rope in min heap with length equal to sum of two extracted minimum lengths ; Finally return total minimum cost for connecting all ropes ; Driver code
class MinHeap { int [ ] harr ; int heap_size ; int capacity ; public MinHeap ( int a [ ] , int size ) { heap_size = size ; capacity = size ; harr = a ; int i = ( heap_size - 1 ) / 2 ; while ( i >= 0 ) { MinHeapify ( i ) ; i -- ; } } void MinHeapify ( int i ) { int l = left ( i ) ; int r = right ( i ) ; int smallest = i ; if ( l < heap_size && harr [ l ] < harr [ i ] ) smallest = l ; if ( r < heap_size && harr [ r ] < harr [ smallest ] ) smallest = r ; if ( smallest != i ) { swap ( i , smallest ) ; MinHeapify ( smallest ) ; } } int parent ( int i ) { return ( i - 1 ) / 2 ; } int left ( int i ) { return ( 2 * i + 1 ) ; } int right ( int i ) { return ( 2 * i + 2 ) ; } int extractMin ( ) { if ( heap_size <= 0 ) return Integer . MAX_VALUE ; if ( heap_size == 1 ) { heap_size -- ; return harr [ 0 ] ; } int root = harr [ 0 ] ; harr [ 0 ] = harr [ heap_size - 1 ] ; heap_size -- ; MinHeapify ( 0 ) ; return root ; } void insertKey ( int k ) { if ( heap_size == capacity ) { System . out . println ( " Overflow : ▁ Could ▁ not ▁ insertKey " ) ; return ; } heap_size ++ ; int i = heap_size - 1 ; harr [ i ] = k ; while ( i != 0 && harr [ parent ( i ) ] > harr [ i ] ) { swap ( i , parent ( i ) ) ; i = parent ( i ) ; } } boolean isSizeOne ( ) { return ( heap_size == 1 ) ; } void swap ( int x , int y ) { int temp = harr [ x ] ; harr [ x ] = harr [ y ] ; harr [ y ] = temp ; } static int minCost ( int len [ ] , int n ) { int cost = 0 ; MinHeap minHeap = new MinHeap ( len , n ) ; while ( ! minHeap . isSizeOne ( ) ) { int min = minHeap . extractMin ( ) ; int sec_min = minHeap . extractMin ( ) ; cost += ( min + sec_min ) ; minHeap . insertKey ( min + sec_min ) ; } return cost ; } public static void main ( String args [ ] ) { int len [ ] = { 4 , 3 , 2 , 6 } ; int size = len . length ; System . out . println ( " Total ▁ cost ▁ for ▁ connecting ▁ ropes ▁ is ▁ " + minCost ( len , size ) ) ; } } ;