fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define MAX_SIZE 100
  4.  
  5. struct heap {
  6.     int box[MAX_SIZE];
  7.     int size;
  8. };
  9.  
  10. void swap(int *u, int *v) {
  11.     int temp;
  12.     temp = *u;
  13.     *u = *v;
  14.     *v = temp;
  15. }
  16.  
  17. void shiftdown(struct heap *h, int p) {
  18.     int s = 2 * p;
  19.     while (s <= h->size) {
  20.         if (s < h->size && h->box[s + 1] < h->box[s])
  21.             s++;
  22.         if (h->box[p] <= h->box[s])
  23.             break;
  24.         swap(&h->box[p], &h->box[s]);
  25.         p = s;
  26.         s = 2 * p;
  27.     }
  28. }
  29.  
  30. void insertMaxHeap(struct heap *h, int item) {
  31.     int i = ++h->size;
  32.     h->box[i] = item;
  33.     while (i > 1 && h->box[i] > h->box[i / 2]) {
  34.         swap(&h->box[i], &h->box[i / 2]);
  35.         i /= 2;
  36.     }
  37. }
  38.  
  39. void insertMinHeap(struct heap *h, int item) {
  40.     int i = ++h->size;
  41.     h->box[i] = item;
  42.     while (i > 1 && h->box[i] < h->box[i / 2]) {
  43.         swap(&h->box[i], &h->box[i / 2]);
  44.         i /= 2;
  45.     }
  46. }
  47.  
  48. int extractMax(struct heap *h) {
  49.     int max = h->box[1];
  50.     h->box[1] = h->box[h->size--];
  51.     shiftdown(h, 1);
  52.     return max;
  53. }
  54.  
  55. int extractMin(struct heap *h) {
  56.     int min = h->box[1];
  57.     h->box[1] = h->box[h->size--];
  58.     shiftdown(h, 1);
  59.     return min;
  60. }
  61.  
  62. void balanceHeaps(struct heap *maxHeap, struct heap *minHeap) {
  63.     if (maxHeap->size > minHeap->size + 1) {
  64.         insertMinHeap(minHeap, extractMax(maxHeap));
  65.     } else if (minHeap->size > maxHeap->size) {
  66.         insertMaxHeap(maxHeap, extractMin(minHeap));
  67.     }
  68. }
  69.  
  70. int findmin(struct heap *h) {
  71.     return h->box[1];
  72. }
  73.  
  74. double findMedian(struct heap *maxHeap, struct heap *minHeap) {
  75.     if (maxHeap->size == minHeap->size) {
  76.         return (findmin(maxHeap) + findmin(minHeap)) / 2.0;
  77.     } else {
  78.         return findmin(maxHeap);
  79.     }
  80. }
  81.  
  82. int main(void) {
  83.     struct heap maxHeap = { .size = 0 };
  84.     struct heap minHeap = { .size = 0 };
  85.     int number;
  86.  
  87.     printf("数字を入力してください。:\n");
  88.  
  89.     while (scanf("%d", &number) != EOF) {
  90.         if (maxHeap.size == 0 || number <= findmin(&maxHeap)) {
  91.             insertMaxHeap(&maxHeap, number);
  92.         } else {
  93.             insertMinHeap(&minHeap, number);
  94.         }
  95.  
  96.         balanceHeaps(&maxHeap, &minHeap);
  97.  
  98.         printf("中央値: %.1f\n", findMedian(&maxHeap, &minHeap));
  99.     }
  100.  
  101.     return 0;
  102. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2
4
stdout
copy 
数字を入力してください。:
中央値: 2.0
中央値: 3.0
https://ideone.com/sXtn8T
language:
C (gcc 8.3)
created:
47 days ago
visibility:
public

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!