我已经在C中实现了滚动中位数计算器（Gist）。它使用max-median-min堆结构：中位数位于heap [0]（位于K项数组的中心）。从heap [1]开始有一个minheap，在heap
[-1]有一个maxheap（使用负索引）。
它与R源中的Turlach实现不完全相同：它支持即时插入值，而R版本一次作用于整个缓冲区。但是我相信时间复杂度是相同的。而且它可以轻松地用于实现整个缓冲区版本
（可能添加一些代码来处理R的“ endrules”） 。
接口：
//Customize for your data Item typetypedef 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); } }}
