Page 259 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

a 힙의 루트(a[0])에 있는 가장 큰 값(10)을 꺼내 배열 마지막 요소(a[9])와 바꿉니다.

b 가장 큰 값을 a[9]로 옮기면 a[9]는 정렬을 마치게 됩니다. 앞에서 살펴본 순서대로 a[0] ~ a[8]의 요소
를 힙으로 만듭니다. 그 결과 두 번째로 큰 요소인 9가 루트에 위치하게 됩니다. 힙의 루트 a[0]에 있는 가
장 큰 값인 9를 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[8]과 바꿉니다.
c 두 번째로 큰 값을 a[8]로 옮기면 a[8] ~ a[9]는 정렬을 마치게 됩니다. 그런 다음 a[0] ~ a[7]의 요소를
힙으로 만듭니다. 그 결과 세 번째로 큰 요소인 8이 루트에 위치하게 됩니다. 힙의 루트 a[0]에 있는 가장
큰 값인 8을 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[7]과 바꿉니다.

이를 반복하면 배열의 마지막부터 큰 값이 차례대로 대입됩니다. 위의 과정을 간단히 정리하
면 다음과 같습니다.

1. 변수 i의 값을 n – 1로 초기화합니다.
2. a[0]과 a[i]를 바꿉니다.
3. a[0], a[1], …, a[i – 1]을 힙으로 만듭니다.
4. i의 값을 1씩 줄여 0이 되면 끝이 납니다. 그렇지 않으면 ‘2’로 돌아갑니다.

이 순서대로 힙 정렬을 수행하면 됩니다. 이때 초기 상태의 배열이 힙 상태가 아닐 수도 있습

니다. 따라서 이 과정을 적용하기 전에 배열을 힙 상태로 만들어야 합니다.

06•정렬 259