include

using namespace std;

// 부모 노드와 자식 노드를 비교하여 큰 값을 위로 올리는 함수 void heapify(int arr[], int n, int i, int& swapCount) { int largest = i; // 루트를 가장 큰 값으로 초기화 int left = 2 * i + 1; int right = 2 * i + 2;

// 왼쪽 자식이 루트보다 크면 largest를 왼쪽 자식으로 설정
if (left < n && arr[left] > arr[largest])
    largest = left;

// 오른쪽 자식이 루트보다 크면 largest를 오른쪽 자식으로 설정
if (right < n && arr[right] > arr[largest])
    largest = right;

// largest가 루트가 아니라면 교환하고 재귀적으로 heapify 호출
if (largest != i) {
    swap(arr[i], arr[largest]);
    swapCount++;
    heapify(arr, n, largest, swapCount);
}

}

// 힙 정렬 함수 int heapSort(int arr[], int n) { int swapCount = 0;

// Max-Heap을 구성
for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i, swapCount);
}

// 요소를 하나씩 추출하며 힙을 재구성
for (int i = n - 1; i > 0; i--) {
    swap(arr[i], arr[0]);

    heapify(arr, i, 0, swapCount);
}

return swapCount;

}

int main() { int n; cin >> n; int arr[n];

for (int i = 0; i < n; i++) {
    cin >> arr[i];
}

int swapCount = heapSort(arr, n);

cout << swapCount << endl;

for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
}
return 0;

}

학교 과제 문제를 푸는 중에 힙정렬 문제를 풀고있었습니다. max heap을 이용해서 오름차순 답을 얻었지만, 교환횟수 정답은 12인데 코드를 천천히 생각해보고 수정해봐도 15가 나옵니다 어떤 부분을 수정해야 12가 나올까요?