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

Subject: Re: [Boost-users] [boost][heap] Which heap to use.
From: Juan Ramírez (jramirez.uy_at_[hidden])
Date: 2016-09-27 16:06:17

>> 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 <degski_at_[hidden]> wrote:

> On 27 September 2016 at 18:55, Oswin Krause <Oswin.Krause_at_ruhr-uni-bochum.
>> de> wrote:
>>
>>> Your solution has linear complexity...
>>>
>>
> It's actually log n.
>
> HAGD,
>
> degski
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

-- 
Juan
:wq