Re: [Boost-users] [boost][heap] Which heap to use.

...

It's actually log n.

Actually, it is not!! Most functions have constant complexity, except for push, which is O(n+ log(n)) = O(n). Let me explain: 1. std::lower_bound is logarithmic in N -> O( log(N) ) 2. vector<T>::insert is linear in the number of elements of the vector -> O(N) vector<T>::insert is your bottleneck here: * In the best case it will move all the elements at the right of the element being inserted. * In the worst case it will have to allocate a new array and the move ALL the elements to the new location. Best regards Juan On Tue, Sep 27, 2016 at 4:14 PM, degski wrote:

On 27 September 2016 at 18:55, Oswin Krause

...

de> wrote:

...

Your solution has linear complexity...

It's actually log n.

HAGD,

degski

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

-- Juan :wq