Re: [boost] Median in Boost.Accumulators

On Sun, 23 Sep 2018 at 12:53, Zach Laine wrote:

On Sun, Sep 23, 2018 at 2:45 PM Lakshay Garg wrote:

...

On Sun, 23 Sep 2018 at 11:59, Zach Laine 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