title: Rolling median algorithm in C
body: <p>I am currently working on an algorithm to implement a rolling median filter (analogous to a rolling mean filter) in C. From my search of the literature, there appear to be two reasonably efficient ways to do it. The first is to sort the initial window of values, then perform a binary search to insert the new value and remove the existing one at each iteration.</p>
  
  <p>The second (from Hardle and Steiger, 1995, JRSS-C, Algorithm 296) builds a double-ended heap structure, with a maxheap on one end, a minheap on the other, and the median in the middle. This yields a linear-time algorithm instead of one that is O(n log n).</p>
  
  <p>Here is my problem: implementing the former is doable, but I need to run this on millions of time series, so efficiency matters a lot. The latter is proving very difficult to implement. I found code in the Trunmed.c file of the code for the stats package of R, but it is rather indecipherable.</p>
  
  <p>Does anyone know of a well-written C implementation for the linear time rolling median algorithm?</p>
  
  <p>Edit: Link to Trunmed.c code <a href="http://google.com/codesearch/p?hl=en&amp;sa=N&amp;cd=1&amp;ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c" rel="noreferrer">http://google.com/codesearch/p?hl=en&amp;sa=N&amp;cd=1&amp;ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c</a></p>