[백준 2220] 힙 정렬

 

 

1부터 n-1 까지 최대힙으로 넣어준다.

마지막으로 배열의 n 자리에 1을 넣어주면 스왑이 가장 많은 힙 구조가 완성된다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n+1];
        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++)
            System.out.print(a[i] + " ");
    }
}