fork download
copy 
  1. /**************************************************************************************************************
  2.    *  Md. Abdulla Al Mamun (Nayon)
  3.    *  ID: 1306001
  4.    *  Session: 2013-2014
  5.    *  Department of Computer Science and Engineering
  6.    *  Begum Rokeya University, Rangpur (BRUR)
  7. ***************************************************************************************************************/
  8. #include <stdio.h>
  9.  
  10. #define MAX 10000
  11. #define swap(typeName, a, b) {typeName _tmp = a; a = b; b = _tmp;}
  12.  
  13. int maxHeap[MAX], minHeap[MAX];
  14. int maxHeapSize, minHeapSize, maxHeapArrayLength, minHeapArrayLength;
  15.  
  16. void maxHeapify(int node)
  17. {
  18. 	int largestNode = node;
  19. 	int lftNode = node*2;
  20. 	int ritNode = lftNode+1;
  21. 	if(lftNode <= maxHeapSize && maxHeap[lftNode] > maxHeap[largestNode]){
  22. 		largestNode = lftNode;
  23. 	}
  24. 	if(ritNode <= maxHeapSize && maxHeap[ritNode] > maxHeap[largestNode]){
  25. 		largestNode = ritNode;
  26. 	}
  27. 	if(largestNode != node){
  28. 		swap(int, maxHeap[largestNode], maxHeap[node]);
  29. 		maxHeapify(largestNode);
  30. 	}
  31. }
  32.  
  33. void minHeapify(int node)
  34. {
  35. 	int smallestNode = node;
  36. 	int lftNode = node*2;
  37. 	int ritNode = lftNode+1;
  38. 	if(lftNode <= minHeapSize && minHeap[lftNode] < minHeap[smallestNode]){
  39. 		smallestNode = lftNode;
  40. 	}
  41. 	if(ritNode <= minHeapSize && minHeap[ritNode] < minHeap[smallestNode]){
  42. 		smallestNode = ritNode;
  43. 	}
  44. 	if(smallestNode != node){
  45. 		swap(int, minHeap[smallestNode], minHeap[node]);
  46. 		minHeapify(smallestNode);
  47. 	}
  48. }
  49.  
  50. void maxHeapMaintain()
  51. {
  52. 	maxHeapSize = maxHeapArrayLength;
  53. 	int node;
  54. 	for(node = maxHeapSize/2; node >= 1; node--){
  55. 		maxHeapify(node);
  56. 	}
  57. }
  58.  
  59. void minHeapMaintain()
  60. {
  61. 	minHeapSize = minHeapArrayLength;
  62. 	int node;
  63. 	for(node = minHeapSize/2; node >= 1; node--){
  64. 		minHeapify(node);
  65. 	}
  66. }
  67.  
  68. int main(int argc, char* argv[])
  69. {
  70. 	int n;
  71. 	maxHeapArrayLength = minHeapArrayLength = 0;
  72. 	double median = 0;
  73. 	int dataNo = 0;
  74. 	int prev;
  75. 	while(scanf("%d", &n) != EOF){
  76. 		dataNo++;
  77. 		if(dataNo <= 2){//if total input data is less than or equal to 2
  78. 			if(dataNo == 1){//first input is itself a median
  79. 				printf("%.1lf\n", 1.0*n);
  80. 				prev = n;
  81. 			}
  82. 			else if(dataNo == 2){//if total input is 2
  83. 				median = (prev+n)/2.0;
  84. 				printf("%.1lf\n", median);
  85. 				if(prev > n){
  86. 					maxHeap[1] = n;
  87. 					minHeap[1] = prev;
  88. 				}
  89. 				else{
  90. 					maxHeap[1] = prev;
  91. 					minHeap[1] = n;
  92. 				}
  93. 				maxHeapArrayLength++;
  94. 				minHeapArrayLength++;
  95. 			}
  96. 			continue;
  97. 		}
  98. 		if(n < maxHeap[1]){//if input n is less than root of the maxHeap then push it to maxHeap
  99. 			maxHeapArrayLength++;
  100. 			maxHeap[maxHeapArrayLength] = n;
  101. 			maxHeapMaintain();
  102. 		}
  103. 		else{//if input n is greater than or equal root of the maxHeap then push it to minHeap
  104. 			minHeapArrayLength++;
  105. 			minHeap[minHeapArrayLength] = n;
  106. 			minHeapMaintain();
  107. 		}
  108.  
  109. 		//balancing the heaps
  110. 		if(maxHeapSize - minHeapSize >= 2){
  111. 			while(maxHeapSize-minHeapSize >= 2){
  112. 				minHeapArrayLength++;
  113. 				minHeap[minHeapArrayLength] = maxHeap[1];
  114. 				minHeapMaintain();
  115. 				swap(int, maxHeap[1], maxHeap[maxHeapArrayLength]);
  116. 				maxHeapArrayLength--;
  117. 				maxHeapMaintain();
  118. 			}
  119. 		}
  120. 		else if(minHeapSize - maxHeapSize >= 2){
  121. 			while(minHeapSize-maxHeapSize >= 2){
  122. 				maxHeapArrayLength++;
  123. 				maxHeap[maxHeapArrayLength] = minHeap[1];
  124. 				maxHeapMaintain();
  125. 				swap(int, minHeap[1], minHeap[minHeapArrayLength]);
  126. 				minHeapArrayLength--;
  127. 				minHeapMaintain();
  128. 			}
  129. 		}
  130.  
  131. 		//claculating median
  132. 		if((maxHeapSize+minHeapSize)%2 == 1){
  133. 			if(maxHeapSize > minHeapSize)
  134. 				median = maxHeap[1];
  135. 			else if(maxHeapSize < minHeapSize)
  136. 				median = minHeap[1];
  137. 		}
  138. 		else{
  139. 			median = (maxHeap[1]+minHeap[1])/2.0;
  140. 		}
  141. 		printf("%.1lf\n", median);
  142. 	}
  143. 	return 0;
  144. }
  145.  
Success #stdin #stdout 0s 9504KB
comments (?)
stdin
copy 
1 2 5 4 5 8 7 6 2 0 3 1 4
stdout
copy 
1.0
1.5
2.0
3.0
4.0
4.5
5.0
5.0
5.0
4.5
4.0
3.5
4.0
https://ideone.com/xBc1pC
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!