Sum of all elements between k1 ' th ▁ and ▁ k2' th smallest elements | C ++ 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 )
#include <bits/stdc++.h> NEW_LINE using namespace std ; int n = 7 ; void minheapify ( int a [ ] , int index ) { int small = index ; int l = 2 * index + 1 ; int r = 2 * index + 2 ; if ( l < n && a [ l ] < a [ small ] ) small = l ; if ( r < n && a [ r ] < a [ small ] ) small = r ; if ( small != index ) { swap ( a [ small ] , a [ index ] ) ; minheapify ( a , small ) ; } } int main ( ) { int i = 0 ; int k1 = 3 ; int k2 = 6 ; int a [ ] = { 20 , 8 , 22 , 4 , 12 , 10 , 14 } ; int ans = 0 ; for ( i = ( n / 2 ) - 1 ; i >= 0 ; i -- ) { minheapify ( a , i ) ; } k1 -- ; k2 -- ; for ( i = 0 ; i <= k1 ; i ++ ) { a [ 0 ] = a [ n - 1 ] ; n -- ; minheapify ( a , 0 ) ; } for ( i = k1 + 1 ; i < k2 ; i ++ ) { ans += a [ 0 ] ; a [ 0 ] = a [ n - 1 ] ; n -- ; minheapify ( a , 0 ) ; } cout << ans ; return 0 ; }