똑똑한 코드 작성을 위한 실전 알고리즘

129

4

장

힙

4.1

최대 이진 힙

이상한 아이디어처럼 보이지만 엔트리가 ‘일부만 정렬’되었다면 어떨까? [그림

4

-

5

]는

17

개 엔

트리가 있는 최대 힙에서 각 엔트리의 우선순위만을 보여준다. 보다시피 레벨

0

에는 최대 힙의

모든 엔트리 중에서 우선순위가 가장 높은 단일 엔트리가 있다.

x

→

y

방향의 화살표가 있으

면 엔트리

x

는 엔트리

y

보다 우선순위가 높다.

그림

4-5

최대 이진 힙 예

이런 엔트리는 정렬된 리스트에서처럼 완전히 정렬된 것이 아니기에 우선순위가 가장 낮은 엔

트리를 찾으려면 잠시 탐색을 해봐야 한다(힌트: 해당 엔트리는 레벨

3

에 있다). 하지만 결과

로 나온 구조는 훌륭한 속성을 가진다. 레벨

1

에는 두 개의 엔트리가 있으며, 그 중 하나는 우

선순위가 두 번째로 높아야 한다(혹은 가장 높은 우선순위와 동일하다 ). 각 레벨

k

(마지막은

제외 )는 엔트리로 가득 차 있고

2

k

개의 엔트리를 포함한다. 맨 밑 레벨에만 일부가 채워져 있

으며 (

16

개가 가능한데

2

개만 있다 ) 왼쪽에서 오른쪽으로 채워진다. 또한 힙에는 우선순위가

같은 엔트리가 있을 수 있다. 우선순위

8

과

14

가 여러 번 보인다.

각 엔트리에서 화살표가

2

개보다 많이 나오지 않도록 해

최대 이진 힙

max

binary

heap

을 구성한다.

우선순위가

15

인 레벨

0

의 엔트리를 ...