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

힙은 루트가 가장 큰(혹은 작은)
값이어야 합니다.
a 4 b 9
모든 부모와 자식의 관계는 항상
6 8 7 8 부모의 값 ≧ 자식의 값이 성립되어야 합니다.

7 5 9 6 5 4
[그림 6-33] 완전이진트리를 힙으로 전환하는 과정

힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않습니다. 예를 들

어 그림 b 에서 형제인 7과 8의 작은 쪽 7은 왼쪽에 있지만 6과 5의 작은 쪽 5는 오른쪽에 있
습니다.
힙은 형제의 대소 관계가 정해져 있지 않은 특성이 있기 때문에 부분순서트리(partial ordered tree)라고도 합니다.

그림 6-34는 힙의 요소를 배열에 저장하는 과정을 나타낸 것입니다. 먼저 가장 위쪽에 있는
루트(9)를 a[0]에 넣습니다. 그리고 한 단계 아래 요소를 왼쪽에서 오른쪽으로 따라 갑니다.

이때 인덱스의 값을 1씩 늘리면서 배열의 각 요소에 힙의 요소를 대입합니다.

0
10
루트(가장 큰 값)
1 2
9 5
０ １ ２ ３ ４ ５ ６ ７ ８ ９
3 4 5 6 10 9 5 8 3 2 4 6 7 1
8 3 2 4
7 8 9
6 7 1

[그림 6-34] 힙 요소와 배열 요소의 대응

이 과정을 거쳐 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계
가 성립합니다.

1. 부모는 a[(i - 1) / 2]
2. 왼쪽 자식은 a[i * 2 + 1]
3. 오른쪽 자식은 a[i * 2 + 2]

정말로 이런 관계가 성립되는지 그림 6-34의 트리를 보면 a[3]의 부모는 a[1]이고 왼쪽, 오른
쪽 자식은 각각 a[7], a[8]입니다. 그리고 a[2]의 부모는 a[0]이고 왼쪽, 오른쪽 자식은 각각

a[5], a[6]입니다. 모두 위의 관계를 만족합니다.

256 C 알고리즘