I'm working on a system with hard real-time constraints in c++ and I need a very fast way to calculate the rolling/moving/streaming median of a set of numbers of size N=100 to 300. Normally this size would be trivial but in this case the algorithm will run about 1000/2000 times per 0.1ms
Every calculation a single value in range (0-1) will be added so (depending on the container) the previous values will already be (weakly) sorted.
Requirements:
No dynamic memory allocation as the median window will be fixed size and any allocation could take too much time
FIFO behaviour in order to remove the last added and insert a new value
Current Approach
Currently I'm considering a min-max heap rolling median approach where you keep a reference to the oldest element and every element has a reference to the next-oldest element. However, I'm unsure how this would work as you would need to remove that element from any position in the heap and it could also be in either of the two heaps.