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

큰 값을 가지는 자식과 위치를 바꿉니다.
c
9 9
1 5  8 5

8 3 2 4 1 3 2 4

6 7 6 7

1의 두 자식은 8과 3입니다. 앞에서나 마찬가지로 큰 값을 가진 8과 바꿉니다. 그러면 1이 왼쪽
으로 내려옵니다.

큰 값을 가지는 자식과 위치를 바꿉니다.
d
9 9
8 5  8 5

1 3 2 4 7 3 2 4

6 7 6 1

1의 두 자식은 6, 7입니다. 큰 값을 가진 오른쪽 자식 7과 바꾸면 1이 오른쪽으로 내려옵니다.
이제 1을 트리의 가장 아랫부분으로 이동시켰으니 작업을 마치게 됩니다.

이렇게 만든 트리는 힙 상태를 유지하게 됩니다. 여기에서는 1을 가장 아래까지 옮겼습니다.
하지만 요소를 항상 끝까지 옮겨야 하는 것은 아닙니다. 옮길 요소보다 왼쪽이나 오른쪽의 두
자식이 더 작으면 바꿀 수 없습니다. 이때 루트를 없앤 다음 다시 힙을 만들기 위해 요소를 알

맞은 위치로 내려보내야 하는데 그 순서는 다음과 같습니다.

1. 루트를 꺼냅니다.
2. 마지막 요소를 루트로 이동합니다.
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복합니다. 이때 자식의
랎값이 작거나 잎에 다다르면 작업이 종료됩니다.

힙 정렬 알고리즘 살펴보기

이제 이 힙을 사용하여 힙 정렬 알고리즘으로 확장하면 됩니다. 그림 6-35를 보며 힙 정렬 알
고리즘의 흐름을 살펴보겠습니다. 다음은 그림에 대한 설명입니다.

258 C 알고리즘