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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk