Sum of all elements between k1 ' th ▁ and ▁ k2' th smallest elements | Python 3 implementation of above approach ; Driver Code ; decreasing value by 1 because we want min heapifying k times and it starts from 0 so we have to decrease it 1 time ; Step 1 : Do extract minimum k1 times ( This step takes O ( K1 Log n ) time ) ; Step 2 : Do extract minimum k2 k1 1 times and sum all extracted elements . ( This step takes O ( ( K2 k1 ) * Log n ) time )
n = 7 NEW_LINE def minheapify ( a , index ) : NEW_LINE INDENT small = index NEW_LINE l = 2 * index + 1 NEW_LINE r = 2 * index + 2 NEW_LINE if ( l < n and a [ l ] < a [ small ] ) : NEW_LINE INDENT small = l NEW_LINE DEDENT if ( r < n and a [ r ] < a [ small ] ) : NEW_LINE INDENT small = r NEW_LINE DEDENT if ( small != index ) : NEW_LINE INDENT ( a [ small ] , a [ index ] ) = ( a [ index ] , a [ small ] ) NEW_LINE minheapify ( a , small ) NEW_LINE DEDENT DEDENT i = 0 NEW_LINE k1 = 3 NEW_LINE k2 = 6 NEW_LINE a = [ 20 , 8 , 22 , 4 , 12 , 10 , 14 ] NEW_LINE ans = 0 NEW_LINE for i in range ( ( n // 2 ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT minheapify ( a , i ) NEW_LINE DEDENT k1 -= 1 NEW_LINE k2 -= 1 NEW_LINE for i in range ( 0 , k1 + 1 ) : NEW_LINE INDENT a [ 0 ] = a [ n - 1 ] NEW_LINE n -= 1 NEW_LINE minheapify ( a , 0 ) NEW_LINE DEDENT for i in range ( k1 + 1 , k2 ) : NEW_LINE INDENT ans += a [ 0 ] NEW_LINE a [ 0 ] = a [ n - 1 ] NEW_LINE n -= 1 NEW_LINE minheapify ( a , 0 ) NEW_LINE DEDENT print ( ans ) NEW_LINE