fork(2) download
  1. //Copyright (c) 2011 ashelly.myopenid.com under <http://www.opensource.org/licenses/mit-license>
  2.  
  3. #include <stdlib.h>
  4.  
  5. //Customize for your data Item type
  6. typedef int Item;
  7. #define ItemLess(a,b) ((a)<(b))
  8. #define ItemMean(a,b) (((a)+(b))/2)
  9.  
  10. typedef struct Mediator_t
  11. {
  12. Item* data; //circular queue of values
  13. int* pos; //index into `heap` for each value
  14. int* heap; //max/median/min heap holding indexes into `data`.
  15. int N; //allocated size.
  16. int idx; //position in circular queue
  17. int ct; //count of items in queue
  18. } Mediator;
  19.  
  20. /*--- Helper Functions ---*/
  21.  
  22. #define minCt(m) (((m)->ct-1)/2) //count of items in minheap
  23. #define maxCt(m) (((m)->ct)/2) //count of items in maxheap
  24.  
  25. //returns 1 if heap[i] < heap[j]
  26. int mmless(Mediator* m, int i, int j)
  27. {
  28. return ItemLess(m->data[m->heap[i]],m->data[m->heap[j]]);
  29. }
  30.  
  31. //swaps items i&j in heap, maintains indexes
  32. int mmexchange(Mediator* m, int i, int j)
  33. {
  34. int t = m->heap[i];
  35. m->heap[i]=m->heap[j];
  36. m->heap[j]=t;
  37. m->pos[m->heap[i]]=i;
  38. m->pos[m->heap[j]]=j;
  39. return 1;
  40. }
  41.  
  42. //swaps items i&j if i<j; returns true if swapped
  43. int mmCmpExch(Mediator* m, int i, int j)
  44. {
  45. return (mmless(m,i,j) && mmexchange(m,i,j));
  46. }
  47.  
  48. //maintains minheap property for all items below i/2.
  49. void minSortDown(Mediator* m, int i)
  50. {
  51. for (; i <= minCt(m); i*=2)
  52. { if (i>1 && i < minCt(m) && mmless(m, i+1, i)) { ++i; }
  53. if (!mmCmpExch(m,i,i/2)) { break; }
  54. }
  55. }
  56.  
  57. //maintains maxheap property for all items below i/2. (negative indexes)
  58. void maxSortDown(Mediator* m, int i)
  59. {
  60. for (; i >= -maxCt(m); i*=2)
  61. { if (i<-1 && i > -maxCt(m) && mmless(m, i, i-1)) { --i; }
  62. if (!mmCmpExch(m,i/2,i)) { break; }
  63. }
  64. }
  65.  
  66. //maintains minheap property for all items above i, including median
  67. //returns true if median changed
  68. int minSortUp(Mediator* m, int i)
  69. {
  70. while (i>0 && mmCmpExch(m,i,i/2)) i/=2;
  71. return (i==0);
  72. }
  73.  
  74. //maintains maxheap property for all items above i, including median
  75. //returns true if median changed
  76. int maxSortUp(Mediator* m, int i)
  77. {
  78. while (i<0 && mmCmpExch(m,i/2,i)) i/=2;
  79. return (i==0);
  80. }
  81.  
  82. /*--- Public Interface ---*/
  83.  
  84.  
  85. //creates new Mediator: to calculate `nItems` running median.
  86. //mallocs single block of memory, caller must free.
  87. Mediator* MediatorNew(int nItems)
  88. {
  89. int size = sizeof(Mediator)+nItems*(sizeof(Item)+sizeof(int)*2);
  90. Mediator* m= malloc(size);
  91. m->data= (Item*)(m+1);
  92. m->pos = (int*) (m->data+nItems);
  93. m->heap = m->pos+nItems + (nItems/2); //points to middle of storage.
  94. m->N=nItems;
  95. m->ct = m->idx = 0;
  96. while (nItems--) //set up initial heap fill pattern: median,max,min,max,...
  97. { m->pos[nItems]= ((nItems+1)/2) * ((nItems&1)?-1:1);
  98. m->heap[m->pos[nItems]]=nItems;
  99. }
  100. return m;
  101. }
  102.  
  103.  
  104. //Inserts item, maintains median in O(lg nItems)
  105. void MediatorInsert(Mediator* m, Item v)
  106. {
  107. int isNew=(m->ct<m->N);
  108. int p = m->pos[m->idx];
  109. Item old = m->data[m->idx];
  110. m->data[m->idx]=v;
  111. m->idx = (m->idx+1) % m->N;
  112. m->ct+=isNew;
  113. if (p>0) //new item is in minHeap
  114. { if (!isNew && ItemLess(old,v)) { minSortDown(m,p*2); }
  115. else if (minSortUp(m,p)) { maxSortDown(m,-1); }
  116. }
  117. else if (p<0) //new item is in maxheap
  118. { if (!isNew && ItemLess(v,old)) { maxSortDown(m,p*2); }
  119. else if (maxSortUp(m,p)) { minSortDown(m, 1); }
  120. }
  121. else //new item is at median
  122. { if (maxCt(m)) { maxSortDown(m,-1); }
  123. if (minCt(m)) { minSortDown(m, 1); }
  124. }
  125. }
  126.  
  127. //returns median item (or average of 2 when item count is even)
  128. Item MediatorMedian(Mediator* m)
  129. {
  130. Item v= m->data[m->heap[0]];
  131. if ((m->ct&1)==0) { v= ItemMean(v,m->data[m->heap[-1]]); }
  132. return v;
  133. }
  134.  
  135.  
  136. /*--- Test Code ---*/
  137. #include <stdio.h>
  138. void PrintMaxHeap(Mediator* m)
  139. {
  140. int i;
  141. if(maxCt(m))
  142. printf("Max: %3d",m->data[m->heap[-1]]);
  143. for (i=2;i<=maxCt(m);++i)
  144. {
  145. printf("|%3d ",m->data[m->heap[-i]]);
  146. if(++i<=maxCt(m)) printf("%3d",m->data[m->heap[-i]]);
  147. }
  148. printf("\n");
  149. }
  150. void PrintMinHeap(Mediator* m)
  151. {
  152. int i;
  153. if(minCt(m))
  154. printf("Min: %3d",m->data[m->heap[1]]);
  155. for (i=2;i<=minCt(m);++i)
  156. {
  157. printf("|%3d ",m->data[m->heap[i]]);
  158. if(++i<=minCt(m)) printf("%3d",m->data[m->heap[i]]);
  159. }
  160. printf("\n");
  161. }
  162.  
  163. void ShowTree(Mediator* m)
  164. {
  165. PrintMaxHeap(m);
  166. printf("Mid: %3d\n",m->data[m->heap[0]]);
  167. PrintMinHeap(m);
  168. printf("\n");
  169. }
  170.  
  171. int main(int argc, char* argv[])
  172. {
  173. int i,v;
  174. Mediator* m = MediatorNew(15);
  175.  
  176. for (i=0;i<30;i++)
  177. {
  178. v = rand()&127;
  179. printf("Inserting %3d \n",v);
  180. MediatorInsert(m,v);
  181. v=MediatorMedian(m);
  182. printf("Median = %3d.\n\n",v);
  183. ShowTree(m);
  184. }
  185. }
Success #stdin #stdout 0s 1852KB
stdin
Standard input is empty
stdout
Inserting 103 
Median = 103.


Mid: 103


Inserting  70 
Median =  86.

Max:  70
Mid: 103


Inserting 105 
Median = 103.

Max:  70
Mid: 103
Min: 105

Inserting 115 
Median = 104.

Max: 103| 70 
Mid: 105
Min: 115

Inserting  81 
Median = 103.

Max:  81| 70 
Mid: 103
Min: 105|115 

Inserting 127 
Median = 104.

Max: 103| 70  81
Mid: 105
Min: 115|127 

Inserting  74 
Median = 103.

Max:  81| 70  74
Mid: 103
Min: 105|127 115

Inserting 108 
Median = 104.

Max: 103| 81  74| 70 
Mid: 105
Min: 108|127 115

Inserting  41 
Median = 103.

Max:  81| 70  74| 41 
Mid: 103
Min: 105|108 115|127 

Inserting  77 
Median =  92.

Max:  81| 77  74| 41  70
Mid: 103
Min: 105|108 115|127 

Inserting  58 
Median =  81.

Max:  77| 70  74| 41  58
Mid:  81
Min: 103|105 115|127 108

Inserting  43 
Median =  79.

Max:  77| 70  74| 41  58| 43 
Mid:  81
Min: 103|105 115|127 108

Inserting 114 
Median =  81.

Max:  77| 70  74| 41  58| 43 
Mid:  81
Min: 103|105 114|127 108|115 

Inserting 123 
Median =  92.

Max:  81| 70  77| 41  58| 43  74
Mid: 103
Min: 105|108 114|127 123|115 

Inserting  99 
Median =  99.

Max:  81| 70  77| 41  58| 43  74
Mid:  99
Min: 103|108 105|127 123|115 114

Inserting  70 
Median =  81.

Max:  77| 70  74| 41  58| 43  70
Mid:  81
Min:  99|108 105|127 123|115 114

Inserting 124 
Median =  99.

Max:  81| 77  74| 41  58| 43  70
Mid:  99
Min: 105|108 114|127 123|115 124

Inserting  66 
Median =  81.

Max:  77| 66  74| 41  58| 43  70
Mid:  81
Min:  99|108 114|127 123|115 124

Inserting  84 
Median =  81.

Max:  77| 66  74| 41  58| 43  70
Mid:  81
Min:  84|108  99|127 123|114 124

Inserting 120 
Median =  84.

Max:  77| 66  74| 41  58| 43  70
Mid:  84
Min:  99|108 114|127 123|120 124

Inserting  27 
Median =  77.

Max:  74| 66  70| 41  58| 43  27
Mid:  77
Min:  84| 99 114|108 123|120 124

Inserting 104 
Median =  84.

Max:  77| 66  70| 41  58| 43  27
Mid:  84
Min:  99|104 114|108 123|120 124

Inserting 103 
Median =  84.

Max:  77| 66  70| 41  58| 43  27
Mid:  84
Min:  99|103 114|104 123|120 124

Inserting  13 
Median =  84.

Max:  77| 66  70| 13  58| 43  27
Mid:  84
Min:  99|103 114|104 123|120 124

Inserting 118 
Median =  99.

Max:  84| 66  70| 13  58| 43  27
Mid:  99
Min: 103|104 114|118 123|120 124

Inserting  90 
Median =  99.

Max:  90| 84  70| 13  66| 43  27
Mid:  99
Min: 103|104 114|118 123|120 124

Inserting  46 
Median =  99.

Max:  90| 84  70| 13  66| 46  27
Mid:  99
Min: 103|104 114|118 123|120 124

Inserting  99 
Median =  99.

Max:  90| 84  70| 13  66| 46  27
Mid:  99
Min:  99|104 103|118 123|120 124

Inserting  51 
Median =  90.

Max:  84| 66  70| 13  51| 46  27
Mid:  90
Min:  99| 99 103|118 104|120 124

Inserting  31 
Median =  84.

Max:  70| 66  46| 13  51| 31  27
Mid:  84
Min:  90| 99 103|118 104|120 124