Minimum cost to merge numbers from 1 to N | Function returns the minimum cost ; Min Heap representation ; Add all elements to heap ; First minimum ; Second minimum ; Multiply them ; Add to the cost ; Push the product into the heap again ; Return the optimal cost ; Driver code
def GetMinCost ( N ) : NEW_LINE INDENT pq = [ ] NEW_LINE for i in range ( 1 , N + 1 , 1 ) : NEW_LINE INDENT pq . append ( i ) NEW_LINE DEDENT pq . sort ( reverse = False ) NEW_LINE cost = 0 NEW_LINE while ( len ( pq ) > 1 ) : NEW_LINE INDENT mini = pq [ 0 ] NEW_LINE pq . remove ( pq [ 0 ] ) NEW_LINE secondmini = pq [ 0 ] NEW_LINE pq . remove ( pq [ 0 ] ) NEW_LINE current = mini * secondmini NEW_LINE cost += current NEW_LINE pq . append ( current ) NEW_LINE pq . sort ( reverse = False ) NEW_LINE DEDENT return cost NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE print ( GetMinCost ( N ) ) NEW_LINE DEDENT