Page 257 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 257
힙 정렬
힙 정렬은 ‘가장 큰 값이 루트에 위치’하는 특징을 이용하는 정렬 알고리즘입니다. 힙에서 가
장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 됩니
다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은
요소에서 다시 가장 큰 값을 구해야 합니다. 다시 말해 힙으로 구성된 10개의 요소에서 가장
큰 값을 없애면 나머지 9개의 요소에서 가장 큰 값을 루트로 정해야 합니다. 따라서 나머지
9개의 요소로 만든 트리도 힙의 형태를 유지할 수 있도록 재구성해야 합니다.
선택 정렬은 가장 작은(혹은 큰) 값을 선택해 정렬하는 알고리즘입니다.
루트를 없애고 힙 상태 유지하기
다음은 루트를 없앤 다음 다시 힙을 만드는 순서를 그림으로 나타낸 것입니다.
a 루트를 없애고 마지막 요소를 루트로 옮깁니다.
10 1
9 5 9 5
8 3 2 4 8 3 2 4
6 7 1 6 7
힙에서 루트인 10을 꺼냅니다. 그런 다음 비어 있는 루트 위치로 힙의 마지막 요소(오른쪽 아래
끝에 있는 자식 요소)인 1을 옮깁니다. 이때 1이외의 요소는 힙 상태를 유지하고 있습니다. 따라
서 이 값만 알맞은 위치로 이동하면 힙 상태를 유지할 수 있습니다.
b 큰 값을 가지는 자식과 위치를 바꿉니다.
1 9
9 5 1 5
8 3 2 4 8 3 2 4
6 7 6 7
이제 루트로 이동시킨 1을 올바른 위치로 보내야 합니다. 현재 이동할 1의 자식은 9와 5입니
다. 힙이 되려면 이 3개의 값 가운데 가장 큰 값이 위쪽에 있어야 합니다. ‘부모의 값 ≧ 자식의
값’이라는 힙의 조건을 만족하려면 두 자식을 비교하여 큰 쪽인 9와 바꾸면 됩니다. 그러면 1
이 왼쪽으로 내려옵니다.
06•정렬 257
