다음 그림과 같은 최대 힙(max heap)을 이용하여 힙 정렬을 수행… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

교환 후 힙 재구성을 마치면 배열은 -, 8, 6, 7, 5, 3, 4, 1, 2, 9가 된다.
9와 4를 교환하면 9는 정렬 완료 위치인 마지막 칸에 고정되고, 힙 크기는 8로 줄어든다. 루트의 4는 두 자식 6과 8 중 큰 8과 교환되어 [3]으로 내려간다.
[3]의 자식은 [6]의 7과 [7]의 1이므로 더 큰 7과 교환해 4가 [6]에 자리 잡는다. [6]은 크기 8 힙에서 자식이 없어 연산이 끝난다.
8, 4, 6, 7, … 배열: 4가 루트 자식 자리에 남아 있어 자식 7보다 작으므로 힙 조건을 어긴다.
8, 5, 4, 6, … 배열: [3]의 4가 자식 7보다 작아 힙 조건을 어기며, 4는 오른쪽 서브트리로만 내려가므로 나올 수 없다.
8, 7, 6, 3, … 배열: 오른쪽 서브트리의 7이 [2]로 옮겨 가 있어, 4 하나만 아래로 내리는 연산 결과와 다르다.