Я реализовал скользящий медианный калькулятор в C здесь (Gist) .Он использует структуру кучи max-median-min: медиана находится в куче [0] (которая находится в центре массива элементов K).Существует minheap, начинающийся с heap [1], и maxheap (использующий отрицательное индексирование) в куче [-1].
Это не совсем то же самое, что реализация Turlach из источника R один поддерживает значения, вставляемые на лету, в то время как версия R действует сразу на весь буфер.Но я считаю, что сложность времени одинакова.И его можно легко использовать для реализации целой версии буфера (возможно, с добавлением некоторого кода для обработки "endrules" R) .
Интерфейс:
//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); }
}
}