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

a 10
정렬되지 않은 부분 정렬을 마친 부분
9 5

8 3 2 4
０ １ ２ ３ ４ ５ ６ ７ ８ ９
10 9 5 8 3 2 4 6 7 1
6 7 1

다시 힙으로 만듭니다. 가장 큰 값인 루트를 꺼내 a[9]로 옮김
b 9

8 5

7 3 2 4
０ １ ２ ３ ４ ５ ６ ７ ８ ❾
9 8 5 7 3 2 4 6 1 10
6 1
다시 힙으로 만듭니다. 가장 큰 값인 루트를 꺼내 a[8]로 옮김

c 8

7 5

6 3 2 4
０ １ ２ ３ ４ ５ ６ ７ ❽ ９
8 7 5 6 3 2 4 1 9 10
1

다시 힙으로 만듭니다. 가장 큰 값인 루트를 꺼내 a[7]로 옮김
d 7

6 5

1 3 2 4
０ １ ２ ３ ４ ５ ６ ❼ ８ ９
7 6 5 1 3 2 4 8 9 10

다시 힙으로 만듭니다. 가장 큰 값인 루트를 꺼내 a[6]으로 옮김
e 6

4 5

1 3 2
０ １ ２ ３ ４ ５ ❻ ７ ８ ９
6 4 5 1 3 2 7 8 9 10

… 생략 …

[그림 6-35] 힙 정렬

260 C 알고리즘