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