Rolling median in C – Turlach implementation

by

I’ve implemented a rolling median calculator in C here (Gist). It uses a max-median-min heap structure: The median is at heap[0] (which is at the center of a K-item array). There is a minheap starting at heap[ 1], and a maxheap (using negative indexing) at heap[-1].
It’s not exactly the same as the Turlach implementation from the R source: This one supports values being inserted on-the-fly, while the R version acts on a whole buffer at once. But I believe the time complexity is the same. And it could easily be used to implement a whole buffer version (possibly with with the addition of some code to handle R’s “endrules”).

Interface:

//Customize for your data Item type
typedef int Item;
#define ItemLess(a,b)  ((a)<(b))
#define ItemMean(a,b)  (((a)+(b))/2)

typedef struct Mediator_t Mediator;

//creates new Mediator: to calculate `nItems` running median. 
//mallocs single block of memory, caller must free.
Mediator* MediatorNew(int nItems);

//returns median item (or average of 2 when item count is even)
Item MediatorMedian(Mediator* m);

//Inserts item, maintains median in O(lg nItems)
void MediatorInsert(Mediator* m, Item v)
{
   int isNew = (m->ct < m->N);
   int p = m->pos[m->idx];
   Item old = m->data[m->idx];
   m->data[m->idx] = v;
   m->idx = (m->idx+1) % m->N;
   m->ct += isNew;
   if (p > 0)         //new item is in minHeap
   {  if (!isNew && ItemLess(old, v)) { minSortDown(m, p*2);  }
      else if (minSortUp(m, p)) { maxSortDown(m,-1); }
   }
   else if (p < 0)   //new item is in maxheap
   {  if (!isNew && ItemLess(v, old)) { maxSortDown(m, p*2); }
      else if (maxSortUp(m, p)) { minSortDown(m, 1); }
   }
   else            //new item is at median
   {  if (maxCt(m)) { maxSortDown(m,-1); }
      if (minCt(m)) { minSortDown(m, 1); }
   }
}

More Related Contents:

  1. Pattern Programmings
  2. the problem is from a algorithm problem I do recently,but I can't gain the right answer [duplicate]
  3. Algorithm to find the smallest number in an array in C [closed]
  4. Recursive C function
  5. How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number [closed]
  6. Finding target sum of two numbers in array
  7. How to remove blank spaces from buffer [closed]
  8. The most efficient way to implement an integer based power function pow(int, int)
  9. hash function for string
  10. Algorithm: efficient way to remove duplicate integers from an array
  11. Building a logarithm function in C without using float type
  12. How can I simplify this working Binary Search code in C?
  13. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  14. C How to “draw” a Binary Tree to the console [closed]
  15. Project Euler Question 14 (Collatz Problem)
  16. How to do unsigned saturating addition in C?
  17. How to find largest triangle in convex hull aside from brute force search
  18. C – How to implement Set data structure?
  19. Print all the permutations of a string in C
  20. Correctness of Sakamoto’s algorithm to find the day of week
  21. Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?
  22. Rolling median algorithm in C
  23. Floating point linear interpolation
  24. Finding the intersecting node from two intersecting linked lists
  25. Finding out the duplicate element in an array
  26. Does C have any tools for doing string addition?
  27. a working non-recursive floodfill algorithm written in C?
  28. Variable Sized Arrays vs calloc in C
  29. Algorithm to pick values from array that sum closest to a target value?
  30. Avoid Overflow when Calculating π by Evaluating a Series Using 16-bit Arithmetic?

Leave a Comment