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

배열로 힙 만들기

그림 6-36과 같은 이진트리가 있다고 가정합니다. 4를 루트로 하는 부분트리( a )는 힙이 아
닙니다. 그러나 왼쪽 자식 8을 루트로 하는 부분트리( b )와 오른쪽 자식 5를 루트로 하는 부분
트리( c )는 모두 힙입니다. 부분트리는 트리의 일부를 지칭하는 말입니다.

＊
힙입니다.
a 4 ＊
힙이 아닙니다.
b 8 c 5 ＊ ＊

7 6 3

[그림 6-36] 왼쪽 부분트리와 오른쪽 부분트리가 힙 상태인 부분트리

앞에서는 루트를 없앤 다음 마지막 요소를 루트로 옮기고 루트로 옮긴 요소를 알맞은 위치로
옮기면서 힙을 만들었습니다. 여기서도 이 방법으로 루트 4를 알맞은 위치로 옮기면 부분트
리 a 를 힙으로 만들 수 있습니다.

이 방법을 이용하면 아랫부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로
전체 배열을 힙으로 만들 수 있습니다. 그림 6-37은 이 내용을 나타낸 것으로, 가장 아랫부분
의 오른쪽 부분트리부터 시작해 왼쪽으로 진행하면서 힙으로 만듭니다. 가장 아랫부분의 단

계가 끝나면 하나 위쪽으로 부분트리 범위를 확장하고 다시 왼쪽으로 진행하면서 부분트리
를 힙으로 만듭니다. 다음은 그림 6-37에 대한 설명입니다.

a 이 트리는 힙이 아닙니다. 마지막(가장 아랫부분의 가장 오른쪽) 부분트리인 {9, 10}을 선택합니다. 요소
9를 내려 힙으로 만듭니다.
b 바로 왼쪽의 부분트리인 {7, 6, 8}을 선택합니다. 요소 7을 오른쪽으로 내려 힙으로 만듭니다.
c 가장 아랫부분의 단계가 끝났습니다. 이제 부분트리의 선택 범위를 위로 한 칸 확장하여 마지막(가장 오른
쪽) 부분트리인 {5, 2, 4}를 선택합니다. 이미 힙이므로 옮길 필요가 없습니다(우연한 힙 상태).
d 바로 왼쪽에 있는 부분트리(3을 루트로 하는 부분트리)를 선택합니다. 여기서는 요소 3을 오른쪽 아래로
내려 힙으로 만듭니다.

e 부분트리의 선택 범위를 위로 한 칸 확장해 트리 전체를 선택합니다. 왼쪽에 있는 자식 10을 루트로 하는
부분트리와 오른쪽에 있는 자식 5를 루트로 하는 부분트리는 모두 힙입니다. 그래서 요소 1을 알맞은 위치
로 내려 힙으로 만들고 끝냅니다.

06•정렬 261