//Copyright (c) 2011 ashelly.myopenid.com under <http://w...content-available-to-author-only...e.org/licenses/mit-license>
 
#include <stdlib.h>
 
//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
{
   Item* data;  //circular queue of values
   int*  pos;   //index into `heap` for each value
   int*  heap;  //max/median/min heap holding indexes into `data`.
   int   N;     //allocated size.
   int   idx;   //position in circular queue
   int   ct;    //count of items in queue
} Mediator;
 
/*--- Helper Functions ---*/
 
#define minCt(m) (((m)->ct-1)/2) //count of items in minheap
#define maxCt(m) (((m)->ct)/2)   //count of items in maxheap 
 
//returns 1 if heap[i] < heap[j]
int mmless(Mediator* m, int i, int j)
{
   return ItemLess(m->data[m->heap[i]],m->data[m->heap[j]]);
}
 
//swaps items i&j in heap, maintains indexes
int mmexchange(Mediator* m, int i, int j)
{
   int t = m->heap[i];
   m->heap[i]=m->heap[j];
   m->heap[j]=t;
   m->pos[m->heap[i]]=i;
   m->pos[m->heap[j]]=j;
   return 1;
}
 
//swaps items i&j if i<j;  returns true if swapped
int mmCmpExch(Mediator* m, int i, int j)
{
   return (mmless(m,i,j) && mmexchange(m,i,j));
}
 
//maintains minheap property for all items below i/2.
void minSortDown(Mediator* m, int i)
{
   for (; i <= minCt(m); i*=2)
   {  if (i>1 && i < minCt(m) && mmless(m, i+1, i)) { ++i; }
      if (!mmCmpExch(m,i,i/2)) { break; }
   }
}
 
//maintains maxheap property for all items below i/2. (negative indexes)
void maxSortDown(Mediator* m, int i)
{
   for (; i >= -maxCt(m); i*=2)
   {  if (i<-1 && i > -maxCt(m) && mmless(m, i, i-1)) { --i; }
      if (!mmCmpExch(m,i/2,i)) { break; }
   }
}
 
//maintains minheap property for all items above i, including median
//returns true if median changed
int minSortUp(Mediator* m, int i)
{
   while (i>0 && mmCmpExch(m,i,i/2)) i/=2;
   return (i==0);
}
 
//maintains maxheap property for all items above i, including median
//returns true if median changed
int maxSortUp(Mediator* m, int i)
{
   while (i<0 && mmCmpExch(m,i/2,i))  i/=2;
   return (i==0);
}
 
/*--- Public Interface ---*/
 
 
//creates new Mediator: to calculate `nItems` running median. 
//mallocs single block of memory, caller must free.
Mediator* MediatorNew(int nItems)
{
   int size = sizeof(Mediator)+nItems*(sizeof(Item)+sizeof(int)*2);
   Mediator* m=  malloc(size);
   m->data= (Item*)(m+1);
   m->pos = (int*) (m->data+nItems);
   m->heap = m->pos+nItems + (nItems/2); //points to middle of storage.
   m->N=nItems;
   m->ct = m->idx = 0;
   while (nItems--)  //set up initial heap fill pattern: median,max,min,max,...
   {  m->pos[nItems]= ((nItems+1)/2) * ((nItems&1)?-1:1);
      m->heap[m->pos[nItems]]=nItems;
   }
   return 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); }
   }
}
 
//returns median item (or average of 2 when item count is even)
Item MediatorMedian(Mediator* m)
{
   Item v= m->data[m->heap[0]];
   if ((m->ct&1)==0) { v= ItemMean(v,m->data[m->heap[-1]]); }
   return v;
}
 
 
/*--- Test Code ---*/
#include <stdio.h>
void PrintMaxHeap(Mediator* m)
{
   int i;
   if(maxCt(m))
      printf("Max: %3d",m->data[m->heap[-1]]);
   for (i=2;i<=maxCt(m);++i)
   {
      printf("|%3d ",m->data[m->heap[-i]]);
      if(++i<=maxCt(m)) printf("%3d",m->data[m->heap[-i]]);
   }
   printf("\n");
}
void PrintMinHeap(Mediator* m)
{
   int i;
   if(minCt(m))
      printf("Min: %3d",m->data[m->heap[1]]);
   for (i=2;i<=minCt(m);++i)
   {
      printf("|%3d ",m->data[m->heap[i]]);
      if(++i<=minCt(m)) printf("%3d",m->data[m->heap[i]]);
   }
   printf("\n");
}
 
void ShowTree(Mediator* m)
{
   PrintMaxHeap(m);
   printf("Mid: %3d\n",m->data[m->heap[0]]);
   PrintMinHeap(m);
   printf("\n");
}
 
int main(int argc, char* argv[])
{
   int i,v;
   Mediator* m = MediatorNew(15);
 
   for (i=0;i<30;i++)
   {
      v = rand()&127;
      printf("Inserting %3d \n",v);
      MediatorInsert(m,v);
      v=MediatorMedian(m);
      printf("Median = %3d.\n\n",v);
      ShowTree(m);
   }
}

Ly9Db3B5cmlnaHQgKGMpIDIwMTEgYXNoZWxseS5teW9wZW5pZC5jb20gdW5kZXIgPGh0dHA6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLm9yZy9saWNlbnNlcy9taXQtbGljZW5zZT4KCiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8vQ3VzdG9taXplIGZvciB5b3VyIGRhdGEgSXRlbSB0eXBlCnR5cGVkZWYgaW50IEl0ZW07CiNkZWZpbmUgSXRlbUxlc3MoYSxiKSAgKChhKTwoYikpCiNkZWZpbmUgSXRlbU1lYW4oYSxiKSAgKCgoYSkrKGIpKS8yKQoKdHlwZWRlZiBzdHJ1Y3QgTWVkaWF0b3JfdAp7CiAgIEl0ZW0qIGRhdGE7ICAvL2NpcmN1bGFyIHF1ZXVlIG9mIHZhbHVlcwogICBpbnQqICBwb3M7ICAgLy9pbmRleCBpbnRvIGBoZWFwYCBmb3IgZWFjaCB2YWx1ZQogICBpbnQqICBoZWFwOyAgLy9tYXgvbWVkaWFuL21pbiBoZWFwIGhvbGRpbmcgaW5kZXhlcyBpbnRvIGBkYXRhYC4KICAgaW50ICAgTjsgICAgIC8vYWxsb2NhdGVkIHNpemUuCiAgIGludCAgIGlkeDsgICAvL3Bvc2l0aW9uIGluIGNpcmN1bGFyIHF1ZXVlCiAgIGludCAgIGN0OyAgICAvL2NvdW50IG9mIGl0ZW1zIGluIHF1ZXVlCn0gTWVkaWF0b3I7CgovKi0tLSBIZWxwZXIgRnVuY3Rpb25zIC0tLSovCgojZGVmaW5lIG1pbkN0KG0pICgoKG0pLT5jdC0xKS8yKSAvL2NvdW50IG9mIGl0ZW1zIGluIG1pbmhlYXAKI2RlZmluZSBtYXhDdChtKSAoKChtKS0+Y3QpLzIpICAgLy9jb3VudCBvZiBpdGVtcyBpbiBtYXhoZWFwIAoKLy9yZXR1cm5zIDEgaWYgaGVhcFtpXSA8IGhlYXBbal0KaW50IG1tbGVzcyhNZWRpYXRvciogbSwgaW50IGksIGludCBqKQp7CiAgIHJldHVybiBJdGVtTGVzcyhtLT5kYXRhW20tPmhlYXBbaV1dLG0tPmRhdGFbbS0+aGVhcFtqXV0pOwp9CgovL3N3YXBzIGl0ZW1zIGkmaiBpbiBoZWFwLCBtYWludGFpbnMgaW5kZXhlcwppbnQgbW1leGNoYW5nZShNZWRpYXRvciogbSwgaW50IGksIGludCBqKQp7CiAgIGludCB0ID0gbS0+aGVhcFtpXTsKICAgbS0+aGVhcFtpXT1tLT5oZWFwW2pdOwogICBtLT5oZWFwW2pdPXQ7CiAgIG0tPnBvc1ttLT5oZWFwW2ldXT1pOwogICBtLT5wb3NbbS0+aGVhcFtqXV09ajsKICAgcmV0dXJuIDE7Cn0KCi8vc3dhcHMgaXRlbXMgaSZqIGlmIGk8ajsgIHJldHVybnMgdHJ1ZSBpZiBzd2FwcGVkCmludCBtbUNtcEV4Y2goTWVkaWF0b3IqIG0sIGludCBpLCBpbnQgaikKewogICByZXR1cm4gKG1tbGVzcyhtLGksaikgJiYgbW1leGNoYW5nZShtLGksaikpOwp9CgovL21haW50YWlucyBtaW5oZWFwIHByb3BlcnR5IGZvciBhbGwgaXRlbXMgYmVsb3cgaS8yLgp2b2lkIG1pblNvcnREb3duKE1lZGlhdG9yKiBtLCBpbnQgaSkKewogICBmb3IgKDsgaSA8PSBtaW5DdChtKTsgaSo9MikKICAgeyAgaWYgKGk+MSAmJiBpIDwgbWluQ3QobSkgJiYgbW1sZXNzKG0sIGkrMSwgaSkpIHsgKytpOyB9CiAgICAgIGlmICghbW1DbXBFeGNoKG0saSxpLzIpKSB7IGJyZWFrOyB9CiAgIH0KfQoKLy9tYWludGFpbnMgbWF4aGVhcCBwcm9wZXJ0eSBmb3IgYWxsIGl0ZW1zIGJlbG93IGkvMi4gKG5lZ2F0aXZlIGluZGV4ZXMpCnZvaWQgbWF4U29ydERvd24oTWVkaWF0b3IqIG0sIGludCBpKQp7CiAgIGZvciAoOyBpID49IC1tYXhDdChtKTsgaSo9MikKICAgeyAgaWYgKGk8LTEgJiYgaSA+IC1tYXhDdChtKSAmJiBtbWxlc3MobSwgaSwgaS0xKSkgeyAtLWk7IH0KICAgICAgaWYgKCFtbUNtcEV4Y2gobSxpLzIsaSkpIHsgYnJlYWs7IH0KICAgfQp9CgovL21haW50YWlucyBtaW5oZWFwIHByb3BlcnR5IGZvciBhbGwgaXRlbXMgYWJvdmUgaSwgaW5jbHVkaW5nIG1lZGlhbgovL3JldHVybnMgdHJ1ZSBpZiBtZWRpYW4gY2hhbmdlZAppbnQgbWluU29ydFVwKE1lZGlhdG9yKiBtLCBpbnQgaSkKewogICB3aGlsZSAoaT4wICYmIG1tQ21wRXhjaChtLGksaS8yKSkgaS89MjsKICAgcmV0dXJuIChpPT0wKTsKfQoKLy9tYWludGFpbnMgbWF4aGVhcCBwcm9wZXJ0eSBmb3IgYWxsIGl0ZW1zIGFib3ZlIGksIGluY2x1ZGluZyBtZWRpYW4KLy9yZXR1cm5zIHRydWUgaWYgbWVkaWFuIGNoYW5nZWQKaW50IG1heFNvcnRVcChNZWRpYXRvciogbSwgaW50IGkpCnsKICAgd2hpbGUgKGk8MCAmJiBtbUNtcEV4Y2gobSxpLzIsaSkpICBpLz0yOwogICByZXR1cm4gKGk9PTApOwp9CgovKi0tLSBQdWJsaWMgSW50ZXJmYWNlIC0tLSovCgoKLy9jcmVhdGVzIG5ldyBNZWRpYXRvcjogdG8gY2FsY3VsYXRlIGBuSXRlbXNgIHJ1bm5pbmcgbWVkaWFuLiAKLy9tYWxsb2NzIHNpbmdsZSBibG9jayBvZiBtZW1vcnksIGNhbGxlciBtdXN0IGZyZWUuCk1lZGlhdG9yKiBNZWRpYXRvck5ldyhpbnQgbkl0ZW1zKQp7CiAgIGludCBzaXplID0gc2l6ZW9mKE1lZGlhdG9yKStuSXRlbXMqKHNpemVvZihJdGVtKStzaXplb2YoaW50KSoyKTsKICAgTWVkaWF0b3IqIG09ICBtYWxsb2Moc2l6ZSk7CiAgIG0tPmRhdGE9IChJdGVtKikobSsxKTsKICAgbS0+cG9zID0gKGludCopIChtLT5kYXRhK25JdGVtcyk7CiAgIG0tPmhlYXAgPSBtLT5wb3Mrbkl0ZW1zICsgKG5JdGVtcy8yKTsgLy9wb2ludHMgdG8gbWlkZGxlIG9mIHN0b3JhZ2UuCiAgIG0tPk49bkl0ZW1zOwogICBtLT5jdCA9IG0tPmlkeCA9IDA7CiAgIHdoaWxlIChuSXRlbXMtLSkgIC8vc2V0IHVwIGluaXRpYWwgaGVhcCBmaWxsIHBhdHRlcm46IG1lZGlhbixtYXgsbWluLG1heCwuLi4KICAgeyAgbS0+cG9zW25JdGVtc109ICgobkl0ZW1zKzEpLzIpICogKChuSXRlbXMmMSk/LTE6MSk7CiAgICAgIG0tPmhlYXBbbS0+cG9zW25JdGVtc11dPW5JdGVtczsKICAgfQogICByZXR1cm4gbTsKfQoKCi8vSW5zZXJ0cyBpdGVtLCBtYWludGFpbnMgbWVkaWFuIGluIE8obGcgbkl0ZW1zKQp2b2lkIE1lZGlhdG9ySW5zZXJ0KE1lZGlhdG9yKiBtLCBJdGVtIHYpCnsKICAgaW50IGlzTmV3PShtLT5jdDxtLT5OKTsKICAgaW50IHAgPSBtLT5wb3NbbS0+aWR4XTsKICAgSXRlbSBvbGQgPSBtLT5kYXRhW20tPmlkeF07CiAgIG0tPmRhdGFbbS0+aWR4XT12OwogICBtLT5pZHggPSAobS0+aWR4KzEpICUgbS0+TjsKICAgbS0+Y3QrPWlzTmV3OwogICBpZiAocD4wKSAgICAgICAgIC8vbmV3IGl0ZW0gaXMgaW4gbWluSGVhcAogICB7ICBpZiAoIWlzTmV3ICYmIEl0ZW1MZXNzKG9sZCx2KSkgeyBtaW5Tb3J0RG93bihtLHAqMik7ICB9CiAgICAgIGVsc2UgaWYgKG1pblNvcnRVcChtLHApKSB7IG1heFNvcnREb3duKG0sLTEpOyB9CiAgIH0KICAgZWxzZSBpZiAocDwwKSAgIC8vbmV3IGl0ZW0gaXMgaW4gbWF4aGVhcAogICB7ICBpZiAoIWlzTmV3ICYmIEl0ZW1MZXNzKHYsb2xkKSkgeyBtYXhTb3J0RG93bihtLHAqMik7IH0KICAgICAgZWxzZSBpZiAobWF4U29ydFVwKG0scCkpIHsgbWluU29ydERvd24obSwgMSk7IH0KICAgfQogICBlbHNlICAgICAgICAgICAgLy9uZXcgaXRlbSBpcyBhdCBtZWRpYW4KICAgeyAgaWYgKG1heEN0KG0pKSB7IG1heFNvcnREb3duKG0sLTEpOyB9CiAgICAgIGlmIChtaW5DdChtKSkgeyBtaW5Tb3J0RG93bihtLCAxKTsgfQogICB9Cn0KCi8vcmV0dXJucyBtZWRpYW4gaXRlbSAob3IgYXZlcmFnZSBvZiAyIHdoZW4gaXRlbSBjb3VudCBpcyBldmVuKQpJdGVtIE1lZGlhdG9yTWVkaWFuKE1lZGlhdG9yKiBtKQp7CiAgIEl0ZW0gdj0gbS0+ZGF0YVttLT5oZWFwWzBdXTsKICAgaWYgKChtLT5jdCYxKT09MCkgeyB2PSBJdGVtTWVhbih2LG0tPmRhdGFbbS0+aGVhcFstMV1dKTsgfQogICByZXR1cm4gdjsKfQoKCi8qLS0tIFRlc3QgQ29kZSAtLS0qLwojaW5jbHVkZSA8c3RkaW8uaD4Kdm9pZCBQcmludE1heEhlYXAoTWVkaWF0b3IqIG0pCnsKICAgaW50IGk7CiAgIGlmKG1heEN0KG0pKQogICAgICBwcmludGYoIk1heDogJTNkIixtLT5kYXRhW20tPmhlYXBbLTFdXSk7CiAgIGZvciAoaT0yO2k8PW1heEN0KG0pOysraSkKICAgewogICAgICBwcmludGYoInwlM2QgIixtLT5kYXRhW20tPmhlYXBbLWldXSk7CiAgICAgIGlmKCsraTw9bWF4Q3QobSkpIHByaW50ZigiJTNkIixtLT5kYXRhW20tPmhlYXBbLWldXSk7CiAgIH0KICAgcHJpbnRmKCJcbiIpOwp9CnZvaWQgUHJpbnRNaW5IZWFwKE1lZGlhdG9yKiBtKQp7CiAgIGludCBpOwogICBpZihtaW5DdChtKSkKICAgICAgcHJpbnRmKCJNaW46ICUzZCIsbS0+ZGF0YVttLT5oZWFwWzFdXSk7CiAgIGZvciAoaT0yO2k8PW1pbkN0KG0pOysraSkKICAgewogICAgICBwcmludGYoInwlM2QgIixtLT5kYXRhW20tPmhlYXBbaV1dKTsKICAgICAgaWYoKytpPD1taW5DdChtKSkgcHJpbnRmKCIlM2QiLG0tPmRhdGFbbS0+aGVhcFtpXV0pOwogICB9CiAgIHByaW50ZigiXG4iKTsKfQoKdm9pZCBTaG93VHJlZShNZWRpYXRvciogbSkKewogICBQcmludE1heEhlYXAobSk7CiAgIHByaW50ZigiTWlkOiAlM2RcbiIsbS0+ZGF0YVttLT5oZWFwWzBdXSk7CiAgIFByaW50TWluSGVhcChtKTsKICAgcHJpbnRmKCJcbiIpOwp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciogYXJndltdKQp7CiAgIGludCBpLHY7CiAgIE1lZGlhdG9yKiBtID0gTWVkaWF0b3JOZXcoMTUpOwoKICAgZm9yIChpPTA7aTwzMDtpKyspCiAgIHsKICAgICAgdiA9IHJhbmQoKSYxMjc7CiAgICAgIHByaW50ZigiSW5zZXJ0aW5nICUzZCBcbiIsdik7CiAgICAgIE1lZGlhdG9ySW5zZXJ0KG0sdik7CiAgICAgIHY9TWVkaWF0b3JNZWRpYW4obSk7CiAgICAgIHByaW50ZigiTWVkaWFuID0gJTNkLlxuXG4iLHYpOwogICAgICBTaG93VHJlZShtKTsKICAgfQp9