std::list< int > heap_merge( std::vector< std::list< int > >& ls )
{
auto cmp = []( auto& x, auto& y )
{
if( y.empty() ) // x > []
{
return false;
}
if( x.empty() ) // [] > y
{
return true;
}
return x.front() > y.front();
};
make_heap( begin( ls ), end( ls ), cmp );
std::list< int > hr;
for( ;; )
{
pop_heap( begin( ls ), end( ls ), cmp );
auto& m = ls.back();
if( m.empty() )
{
break;
}
hr.push_back( m.front() );
m.pop_front();
push_heap( begin( ls ), end( ls ), cmp );
}
return hr;
}
