2220번: 힙 정렬

https://www.acmicpc.net/problem/2220


$O(n\lg n)$

1을 힙의 가장 뒤에 있도록(가장 높은 레벨에서 오른쪽에 위치) 유지하면 swap 횟수를 최대로 할 수 있다.
아무것도 없는 집합에서 출발하여 거꾸로 힙에 수를 추가하며 만들면 이러한 특성을 만족하는 배열을 얻을 수 있다.

#include<cstdio>
int n, a[100001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 1; j /= 2) a[j] = a[j / 2];
        a[1] = i + 1;
    }
    a[n] = 1;
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}