Algorithm idea #5
Description
Would you be open to including an algorithm that is optimized for large window sizes (e.g. 10,000-50,000)?
Something with O(log(window_size)) runtime. Specifically, what I have in mind is to maintain a min-heap of values below a predetermined percentile and a max-heap of values above it. Also maintain a circular queue of elements in the window with pointers from those elements to the heap nodes that contain them. The heaps would support O(log n) insertion and removal at the head and also O(log n) removal of an arbitrary element given a pointer to that element.
If there is more than 2 percentile of interest, there could be double ended queues between the percentiles.
The percentiles would have to be predetermined at construction time.
Is this something you would be willing to include in this package or should I make a different package for it?