#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;
}