Re: [boost] Median in Boost.Accumulators

Subject: Re: [boost] Median in Boost.Accumulators
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2018-09-23 15:31:11

On Sun, 23 Sep 2018 at 07:29, Bjorn Reese via Boost
<boost_at_[hidden]> wrote:
>
> On 09/23/18 04:21, Lakshay Garg via Boost wrote:
>
> > I rolled up my custom implementation of the algorithm and
> > used it for my project. I wanted to check if people on
> > this list might be interested in such an implementation
> > for Boost.Accumulators in which case I can try to adapt my
> > implementation and send a PR.
>
> Boost.Accumulators does not seem to be actively maintained.

Is there a standard protocol for dealing with unmaintained
projects? It is sad to see such a useful library without a maintainer.
I would happily volunteer for maintaining this library but by
no means do I have the required skills/expertise for this task.

> > Performance characteristics: For a stream of n numbers, the
> > memory required is O(n). Median can be queried at any point
> > of time in O(1) and adding all the elements costs O(nlog(n))
>
> Sounds like you keep two ordered lists (e.g. std::set) of equal size.
> Then the median is the first element in the second list.

I'm using two std::priority_queues where one is a max heap and
the other is a min heap.