다음 애플릿은 heap sort 에서 초기 heap 을 만든 후 소트하는 과정을 보이고 있다.

//// [동작보기 클릭] //////

입력

• 첫 줄에는 데이터 수 n 이 주어진다. n 은 1000 이하.
• 다음 줄에는 n 개의 수가 입력으로 주어진다. 각 수는 -1000 에서 1000 사이 정수이다.

출력

left child 와 right child 가 동일할 경우 left child 가 우선한다.

입출력 예

입력

7
6 2 9 8 3 4 7

출력

9 8 7 2 3 4 6
6 3 4 2

채점데이터:pl0892029