#include <stdio.h>
#define MAX_SIZE 100
struct heap {
int box[MAX_SIZE];
int size;
};
void swap(int *u, int *v) {
int temp;
temp = *u;
*u = *v;
*v = temp;
}
void shiftdown(struct heap *h, int p) {
int s = 2 * p;
while (s <= h->size) {
if (s < h->size && h->box[s + 1] < h->box[s])
s++;
if (h->box[p] <= h->box[s])
break;
swap(&h->box[p], &h->box[s]);
p = s;
s = 2 * p;
}
}
void insertMaxHeap(struct heap *h, int item) {
int i = ++h->size;
h->box[i] = item;
while (i > 1 && h->box[i] > h->box[i / 2]) {
swap(&h->box[i], &h->box[i / 2]);
i /= 2;
}
}
void insertMinHeap(struct heap *h, int item) {
int i = ++h->size;
h->box[i] = item;
while (i > 1 && h->box[i] < h->box[i / 2]) {
swap(&h->box[i], &h->box[i / 2]);
i /= 2;
}
}
int extractMax(struct heap *h) {
int max = h->box[1];
h->box[1] = h->box[h->size--];
shiftdown(h, 1);
return max;
}
int extractMin(struct heap *h) {
int min = h->box[1];
h->box[1] = h->box[h->size--];
shiftdown(h, 1);
return min;
}
void balanceHeaps(struct heap *maxHeap, struct heap *minHeap) {
if (maxHeap->size > minHeap->size + 1) {
insertMinHeap(minHeap, extractMax(maxHeap));
} else if (minHeap->size > maxHeap->size) {
insertMaxHeap(maxHeap, extractMin(minHeap));
}
}
double findMedian(struct heap *maxHeap, struct heap *minHeap) {
if (maxHeap->size == minHeap->size) {
return (maxHeap->box[1] + minHeap->box[1]) / 2.0;
} else {
return maxHeap->box[1];
}
}
int main(void) {
struct heap maxHeap = { .size = 0 };
struct heap minHeap = { .size = 0 };
int number;
printf("数字を入力してください (終了するにはCtrl+Dを押してください):\n");
while (scanf("%d", &number
) != EOF
) { if (maxHeap.size == 0 || number <= maxHeap.box[1]) {
insertMaxHeap(&maxHeap, number);
} else {
insertMinHeap(&minHeap, number);
}
balanceHeaps(&maxHeap, &minHeap);
printf("現在の中央値: %.1f\n", findMedian
(&maxHeap
, &minHeap
)); }
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIE1BWF9TSVpFIDEwMAoKc3RydWN0IGhlYXAgewogICAgaW50IGJveFtNQVhfU0laRV07CiAgICBpbnQgc2l6ZTsKfTsKCnZvaWQgc3dhcChpbnQgKnUsIGludCAqdikgewogICAgaW50IHRlbXA7CiAgICB0ZW1wID0gKnU7CiAgICAqdSA9ICp2OwogICAgKnYgPSB0ZW1wOwp9Cgp2b2lkIHNoaWZ0ZG93bihzdHJ1Y3QgaGVhcCAqaCwgaW50IHApIHsKICAgIGludCBzID0gMiAqIHA7CiAgICB3aGlsZSAocyA8PSBoLT5zaXplKSB7CiAgICAgICAgaWYgKHMgPCBoLT5zaXplICYmIGgtPmJveFtzICsgMV0gPCBoLT5ib3hbc10pCiAgICAgICAgICAgIHMrKzsKICAgICAgICBpZiAoaC0+Ym94W3BdIDw9IGgtPmJveFtzXSkKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgc3dhcCgmaC0+Ym94W3BdLCAmaC0+Ym94W3NdKTsKICAgICAgICBwID0gczsKICAgICAgICBzID0gMiAqIHA7CiAgICB9Cn0KCnZvaWQgaW5zZXJ0TWF4SGVhcChzdHJ1Y3QgaGVhcCAqaCwgaW50IGl0ZW0pIHsKICAgIGludCBpID0gKytoLT5zaXplOwogICAgaC0+Ym94W2ldID0gaXRlbTsKICAgIHdoaWxlIChpID4gMSAmJiBoLT5ib3hbaV0gPiBoLT5ib3hbaSAvIDJdKSB7CiAgICAgICAgc3dhcCgmaC0+Ym94W2ldLCAmaC0+Ym94W2kgLyAyXSk7CiAgICAgICAgaSAvPSAyOwogICAgfQp9Cgp2b2lkIGluc2VydE1pbkhlYXAoc3RydWN0IGhlYXAgKmgsIGludCBpdGVtKSB7CiAgICBpbnQgaSA9ICsraC0+c2l6ZTsKICAgIGgtPmJveFtpXSA9IGl0ZW07CiAgICB3aGlsZSAoaSA+IDEgJiYgaC0+Ym94W2ldIDwgaC0+Ym94W2kgLyAyXSkgewogICAgICAgIHN3YXAoJmgtPmJveFtpXSwgJmgtPmJveFtpIC8gMl0pOwogICAgICAgIGkgLz0gMjsKICAgIH0KfQoKaW50IGV4dHJhY3RNYXgoc3RydWN0IGhlYXAgKmgpIHsKICAgIGludCBtYXggPSBoLT5ib3hbMV07CiAgICBoLT5ib3hbMV0gPSBoLT5ib3hbaC0+c2l6ZS0tXTsKICAgIHNoaWZ0ZG93bihoLCAxKTsKICAgIHJldHVybiBtYXg7Cn0KCmludCBleHRyYWN0TWluKHN0cnVjdCBoZWFwICpoKSB7CiAgICBpbnQgbWluID0gaC0+Ym94WzFdOwogICAgaC0+Ym94WzFdID0gaC0+Ym94W2gtPnNpemUtLV07CiAgICBzaGlmdGRvd24oaCwgMSk7CiAgICByZXR1cm4gbWluOwp9Cgp2b2lkIGJhbGFuY2VIZWFwcyhzdHJ1Y3QgaGVhcCAqbWF4SGVhcCwgc3RydWN0IGhlYXAgKm1pbkhlYXApIHsKICAgIGlmIChtYXhIZWFwLT5zaXplID4gbWluSGVhcC0+c2l6ZSArIDEpIHsKICAgICAgICBpbnNlcnRNaW5IZWFwKG1pbkhlYXAsIGV4dHJhY3RNYXgobWF4SGVhcCkpOwogICAgfSBlbHNlIGlmIChtaW5IZWFwLT5zaXplID4gbWF4SGVhcC0+c2l6ZSkgewogICAgICAgIGluc2VydE1heEhlYXAobWF4SGVhcCwgZXh0cmFjdE1pbihtaW5IZWFwKSk7CiAgICB9Cn0KCmRvdWJsZSBmaW5kTWVkaWFuKHN0cnVjdCBoZWFwICptYXhIZWFwLCBzdHJ1Y3QgaGVhcCAqbWluSGVhcCkgewogICAgaWYgKG1heEhlYXAtPnNpemUgPT0gbWluSGVhcC0+c2l6ZSkgewogICAgICAgIHJldHVybiAobWF4SGVhcC0+Ym94WzFdICsgbWluSGVhcC0+Ym94WzFdKSAvIDIuMDsKICAgIH0gZWxzZSB7CiAgICAgICAgcmV0dXJuIG1heEhlYXAtPmJveFsxXTsKICAgIH0KfQoKaW50IG1haW4odm9pZCkgewogICAgc3RydWN0IGhlYXAgbWF4SGVhcCA9IHsgLnNpemUgPSAwIH07CiAgICBzdHJ1Y3QgaGVhcCBtaW5IZWFwID0geyAuc2l6ZSA9IDAgfTsKICAgIGludCBudW1iZXI7CgogICAgcHJpbnRmKCLmlbDlrZfjgpLlhaXlipvjgZfjgabjgY/jgaDjgZXjgYQgKOe1guS6huOBmeOCi+OBq+OBr0N0cmwrROOCkuaKvOOBl+OBpuOBj+OBoOOBleOBhCk6XG4iKTsKCiAgICB3aGlsZSAoc2NhbmYoIiVkIiwgJm51bWJlcikgIT0gRU9GKSB7CiAgICAgICAgaWYgKG1heEhlYXAuc2l6ZSA9PSAwIHx8IG51bWJlciA8PSBtYXhIZWFwLmJveFsxXSkgewogICAgICAgICAgICBpbnNlcnRNYXhIZWFwKCZtYXhIZWFwLCBudW1iZXIpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGluc2VydE1pbkhlYXAoJm1pbkhlYXAsIG51bWJlcik7CiAgICAgICAgfQoKICAgICAgICBiYWxhbmNlSGVhcHMoJm1heEhlYXAsICZtaW5IZWFwKTsKCiAgICAgICAgcHJpbnRmKCLnj77lnKjjga7kuK3lpK7lgKQ6ICUuMWZcbiIsIGZpbmRNZWRpYW4oJm1heEhlYXAsICZtaW5IZWFwKSk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=