# dynamic binary search

Suppose I have a time series of values $v_1, \dotsc, v_n, \dots,$ (think of the data as being generated by repeated function calls, like a Python generator, or being captured in real time) and I want to maintain a window of the last $k$ values in sorted order. If $k$ were small, I could just keep re-sorting, but assume that $k$ is large. If I were doing this in C (or some such), this would be easy: I would find where each new value goes by binary search (then delete the "stale" value), but in Mathematica nothing leaps to mind. Any suggestions? One could ask a similar question in higher dimensions (where one is asking for a dynamic voronoi triangulation or kd tree), but one thing at a time...

• If you ultimately need all values in sorted order, you should sort the full data set first. – David G. Stork Mar 31 '17 at 23:57
• @DavidG.Stork I do not, and think of the data as being generated on the fly, so I know the past, but not the future. – Igor Rivin Mar 31 '17 at 23:58
• I recommend you edit your question to clarify your key point about data being generated "on the fly." – David G. Stork Apr 1 '17 at 0:06
• @DavidG.Stork I say this in the parenthetical comment at the end (we are trying to maintain a dynamic Voronoi triangulation (in one dimension :)) – Igor Rivin Apr 1 '17 at 0:37
• I think this could be implemented with a priority queue see mathematica.stackexchange.com/q/31968/36788 – mikado Apr 1 '17 at 16:27