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

51 printf("x[%d] = %d\n", i, x[i]);
52 free(x); /* 배열 해제 */
53
54 return 0;
55 }

downheap 함수
배열 a 가운데 a[left] ~ a[right]의 요소를 힙으로 만드는 함수입니다. a[left] 이외에는 모두

힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만듭니다.
앞에서 공부한 ‘루트를 없애고 힙 상태 유지하기’에 대한 내용입니다.

heapsort 함수
요소의 개수가 n개인 배열 a를 힙 정렬하는 함수입니다. 아래의 2단계로 구성됩니다.

1 downheap 함수를 사용하여 배열 a를 힙으로 만듭니다.
2 루트(a[0])에 있는 가장 큰 값을 빼내어 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만
드는 과정을 반복하여 정렬을 수행합니다.

1 은 ‘배열을 힙으로 만들기’에 대한 내용이고, 2 는 ‘힙 정렬 알고리즘 살펴보기’에 대한 내용입니다.

06•정렬 265