#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));
}
}
int findmin(struct heap *h) {
return h->box[1];
}
double findMedian(struct heap *maxHeap, struct heap *minHeap) {
if (maxHeap->size == minHeap->size) {
return (findmin(maxHeap) + findmin(minHeap)) / 2.0;
} else {
return findmin(maxHeap);
}
}
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 <= findmin(&maxHeap)) {
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+c2l6ZSkgewogICAgICAgIGluc2VydE1heEhlYXAobWF4SGVhcCwgZXh0cmFjdE1pbihtaW5IZWFwKSk7CiAgICB9Cn0KCmludCBmaW5kbWluKHN0cnVjdCBoZWFwICpoKSB7CiAgICByZXR1cm4gaC0+Ym94WzFdOwp9Cgpkb3VibGUgZmluZE1lZGlhbihzdHJ1Y3QgaGVhcCAqbWF4SGVhcCwgc3RydWN0IGhlYXAgKm1pbkhlYXApIHsKICAgIGlmIChtYXhIZWFwLT5zaXplID09IG1pbkhlYXAtPnNpemUpIHsKICAgICAgICByZXR1cm4gKGZpbmRtaW4obWF4SGVhcCkgKyBmaW5kbWluKG1pbkhlYXApKSAvIDIuMDsKICAgIH0gZWxzZSB7CiAgICAgICAgcmV0dXJuIGZpbmRtaW4obWF4SGVhcCk7CiAgICB9Cn0KCmludCBtYWluKHZvaWQpIHsKICAgIHN0cnVjdCBoZWFwIG1heEhlYXAgPSB7IC5zaXplID0gMCB9OwogICAgc3RydWN0IGhlYXAgbWluSGVhcCA9IHsgLnNpemUgPSAwIH07CiAgICBpbnQgbnVtYmVyOwoKICAgIHByaW50Zigi5pWw5a2X44KS5YWl5Yqb44GX44Gm44GP44Gg44GV44GEICjntYLkuobjgZnjgovjgavjga9DdHJsK0TjgpLmirzjgZfjgabjgY/jgaDjgZXjgYQpOlxuIik7CgogICAgd2hpbGUgKHNjYW5mKCIlZCIsICZudW1iZXIpICE9IEVPRikgewogICAgICAgIGlmIChtYXhIZWFwLnNpemUgPT0gMCB8fCBudW1iZXIgPD0gZmluZG1pbigmbWF4SGVhcCkpIHsKICAgICAgICAgICAgaW5zZXJ0TWF4SGVhcCgmbWF4SGVhcCwgbnVtYmVyKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBpbnNlcnRNaW5IZWFwKCZtaW5IZWFwLCBudW1iZXIpOwogICAgICAgIH0KCiAgICAgICAgYmFsYW5jZUhlYXBzKCZtYXhIZWFwLCAmbWluSGVhcCk7CgogICAgICAgIHByaW50Zigi54++5Zyo44Gu5Lit5aSu5YCkOiAlLjFmXG4iLCBmaW5kTWVkaWFuKCZtYXhIZWFwLCAmbWluSGVhcCkpOwogICAgfQoKICAgIHJldHVybiAwOwp9