#include <stdio.h>
#include <stdlib.h>
 
#define MAX_SIZE 100
 
// ヒープを管理する構造体
typedef struct {
    int data[MAX_SIZE];
    int size;
} HeapA;
 
// 2つの値を入れ替える関数
void swapA(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
// 最小ヒープを維持するためのダウンヒープ処理
void downHeapA(HeapA *h, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
 
    if (left < h->size && h->data[left] < h->data[smallest])
        smallest = left;
 
    if (right < h->size && h->data[right] < h->data[smallest])
        smallest = right;
 
    if (smallest != i) {
        swapA(&h->data[i], &h->data[smallest]);
        downHeapA(h, smallest);
    }
}
 
// ヒープソート（降順）を行う関数
void heapSortDescending(int arr[], int n) {
    HeapA h;
    h.size = n;
 
    // 1. 配列のデータをヒープ構造体にコピー
    for (int i = 0; i < n; i++) {
        h.data[i] = arr[i];
    }
 
    // 2. 最小ヒープの構築 (ボトムアップ)
    for (int i = (n / 2) - 1; i >= 0; i--) {
        downHeapA(&h, i);
    }
 
    // 3. 最小値（根）を取り出し、配列の後ろから詰めていくことで降順にする
    for (int i = 0; i < n; i++) {
        arr[i] = h.data[0];            // 現在の最小値を取り出す
        h.data[0] = h.data[h.size - 1]; // 末尾の要素を根に移動
        h.size--;                       // サイズを減らす
        downHeapA(&h, 0);               // 再度最小ヒープを再構築
    }
}
 
int main() {
    int arr[] = {31, 14, 59, 26, 53, 58, 97};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("元の配列:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n\n");
 
    heapSortDescending(arr, n);
 
    printf("ヒープソート後（降順）:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCiNkZWZpbmUgTUFYX1NJWkUgMTAwCgovLyDjg5Ljg7zjg5fjgpLnrqHnkIbjgZnjgovmp4vpgKDkvZMKdHlwZWRlZiBzdHJ1Y3QgewogICAgaW50IGRhdGFbTUFYX1NJWkVdOwogICAgaW50IHNpemU7Cn0gSGVhcEE7CgovLyAy44Gk44Gu5YCk44KS5YWl44KM5pu/44GI44KL6Zai5pWwCnZvaWQgc3dhcEEoaW50ICphLCBpbnQgKmIpIHsKICAgIGludCB0ZW1wID0gKmE7CiAgICAqYSA9ICpiOwogICAgKmIgPSB0ZW1wOwp9CgovLyDmnIDlsI/jg5Ljg7zjg5fjgpLntq3mjIHjgZnjgovjgZ/jgoHjga7jg4Djgqbjg7Pjg5Ljg7zjg5flh6bnkIYKdm9pZCBkb3duSGVhcEEoSGVhcEEgKmgsIGludCBpKSB7CiAgICBpbnQgc21hbGxlc3QgPSBpOwogICAgaW50IGxlZnQgPSAyICogaSArIDE7CiAgICBpbnQgcmlnaHQgPSAyICogaSArIDI7CgogICAgaWYgKGxlZnQgPCBoLT5zaXplICYmIGgtPmRhdGFbbGVmdF0gPCBoLT5kYXRhW3NtYWxsZXN0XSkKICAgICAgICBzbWFsbGVzdCA9IGxlZnQ7CgogICAgaWYgKHJpZ2h0IDwgaC0+c2l6ZSAmJiBoLT5kYXRhW3JpZ2h0XSA8IGgtPmRhdGFbc21hbGxlc3RdKQogICAgICAgIHNtYWxsZXN0ID0gcmlnaHQ7CgogICAgaWYgKHNtYWxsZXN0ICE9IGkpIHsKICAgICAgICBzd2FwQSgmaC0+ZGF0YVtpXSwgJmgtPmRhdGFbc21hbGxlc3RdKTsKICAgICAgICBkb3duSGVhcEEoaCwgc21hbGxlc3QpOwogICAgfQp9CgovLyDjg5Ljg7zjg5fjgr3jg7zjg4jvvIjpmY3poIbvvInjgpLooYzjgYbplqLmlbAKdm9pZCBoZWFwU29ydERlc2NlbmRpbmcoaW50IGFycltdLCBpbnQgbikgewogICAgSGVhcEEgaDsKICAgIGguc2l6ZSA9IG47CgogICAgLy8gMS4g6YWN5YiX44Gu44OH44O844K/44KS44OS44O844OX5qeL6YCg5L2T44Gr44Kz44OU44O8CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGguZGF0YVtpXSA9IGFycltpXTsKICAgIH0KCiAgICAvLyAyLiDmnIDlsI/jg5Ljg7zjg5fjga7mp4vnr4kgKOODnOODiOODoOOCouODg+ODlykKICAgIGZvciAoaW50IGkgPSAobiAvIDIpIC0gMTsgaSA+PSAwOyBpLS0pIHsKICAgICAgICBkb3duSGVhcEEoJmgsIGkpOwogICAgfQoKICAgIC8vIDMuIOacgOWwj+WApO+8iOague+8ieOCkuWPluOCiuWHuuOBl+OAgemFjeWIl+OBruW+jOOCjeOBi+OCieipsOOCgeOBpuOBhOOBj+OBk+OBqOOBp+mZjemghuOBq+OBmeOCiwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBhcnJbaV0gPSBoLmRhdGFbMF07ICAgICAgICAgICAgLy8g54++5Zyo44Gu5pyA5bCP5YCk44KS5Y+W44KK5Ye644GZCiAgICAgICAgaC5kYXRhWzBdID0gaC5kYXRhW2guc2l6ZSAtIDFdOyAvLyDmnKvlsL7jga7opoHntKDjgpLmoLnjgavnp7vli5UKICAgICAgICBoLnNpemUtLTsgICAgICAgICAgICAgICAgICAgICAgIC8vIOOCteOCpOOCuuOCkua4m+OCieOBmQogICAgICAgIGRvd25IZWFwQSgmaCwgMCk7ICAgICAgICAgICAgICAgLy8g5YaN5bqm5pyA5bCP44OS44O844OX44KS5YaN5qeL56+JCiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW50IGFycltdID0gezMxLCAxNCwgNTksIDI2LCA1MywgNTgsIDk3fTsKICAgIGludCBuID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKCiAgICBwcmludGYoIuWFg+OBrumFjeWIlzpcbiIpOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHByaW50ZigiJWQgIiwgYXJyW2ldKTsKICAgIHByaW50ZigiXG5cbiIpOwoKICAgIGhlYXBTb3J0RGVzY2VuZGluZyhhcnIsIG4pOwoKICAgIHByaW50Zigi44OS44O844OX44K944O844OI5b6M77yI6ZmN6aCG77yJOlxuIik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgcHJpbnRmKCIlZCAiLCBhcnJbaV0pOwogICAgcHJpbnRmKCJcbiIpOwoKICAgIHJldHVybiAwOwp9