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

Subject: Re: [Boost-users] [boost][heap] Which heap to use.
From: Oswin Krause (Oswin.Krause_at_[hidden])
Date: 2016-09-27 16:30:00

Hi,
On 2016-09-27 21:14, degski wrote:
>> On 27 September 2016 at 18:55, Oswin Krause
>> <Oswin.Krause_at_[hidden]> wrote:
>> 
>>> Your solution has linear complexity...
> 
> It's actually log n.

The worst case is insertion of objects with priority 1...n in that 
order. As your elements are sorted so that low priorities are on the 
right, your push function will always insert the new elements as the 
first element, thus all previously inserted elements are copied one 
element to the right(see complexity of std::vector::insert)

=> O(n) for every inserted elements and overall O(n^2/2) copies.

Best,
Oswin