Re: [boost] Median in Boost.Accumulators

Subject: Re: [boost] Median in Boost.Accumulators
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2018-09-23 19:57:37

On Sun, 23 Sep 2018 at 12:53, Zach Laine <whatwasthataddress_at_[hidden]> wrote:
>
> On Sun, Sep 23, 2018 at 2:45 PM Lakshay Garg <lakshayg373_at_[hidden]> wrote:
>>
>> On Sun, 23 Sep 2018 at 11:59, Zach Laine <whatwasthataddress_at_[hidden]> wrote:
>> > Also, what if I don't actually call get() very often?
>>
>> If get() is not called very often, then I guess just using a plain vector and
>> calling nth_element on it would be the best approach.
>>
>> > Is there any way to take advantage of make_heap()'s O(n) characteristics,
>> > and avoid doing an O(n) push_heap() n times?  I can't think of one offhand,
>> > just curious.
>>
>> The complexity of push_heap is actually O(log(n)) and not O(n)
>
> [make.heap] says:
>
>  Complexity: At most 3 * (last - first) comparisons.
>

Correct! complexity for make_heap is O(n) and complexity for push_heap
is O(logn).

https://en.cppreference.com/w/cpp/algorithm/make_heap
https://en.cppreference.com/w/cpp/algorithm/push_heap