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

132

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

지 않다.

(

2

)

는 레벨

0

에 있는 우선순위가

4

인 엔트리가 두 자식 엔트리의 우선순위보다 작으므

로 유효하지 않다.

NOTE

_ (

2

)는 사실 각 부모 엔트리의 우선순위가 자식 엔트리의 우선순위보다 작거나 같은 값을 가지는 최

소 이진 힙에서 유효한 예다. 최소 이진 힙은

7

장에서 다룬다.

enqueue

()

나

dequeue

()

(최대 힙에서 우선순위가 가장 높은 값을 제거 ) 후에도 두 힙 속성을

만족하도록 해야 한다. 그러면 이전 [표

4

-

1

]에서 설명했던

enqueue

()

와

dequeue

()

가 최악

의 경우 성능이

O

(

N

)인 접근 방식을 크게 개선한

O

(

log

N

)으로 수행됨을 입증할 수 있다.

4.2

(값, 우선순위) 삽입하기

최대 이진 힙에서

enqueue

(

value

,

priority

)

가 수행되면 새로운 엔트리는 어디에 들어가

야 할까? 다음과 같은 항상 동일한 전략으로 동작한다.

●

새로운 엔트리는 마지막 레벨에 가용한 비어 있는 위치에 넣는다.

●

레벨이 가득 차 있다면 새로운 레벨을 추가해 힙을 확장하고, 새로운 엔트리를 그 레벨의 가장 왼쪽 위치

에 넣는다.

[그림

4

-

8

]에서 우선순위가

12

인 새로운 노드는 레벨

4

의 세 번째 위치에 삽입된다. 이때 힙

모양 속성을 만족한다 (레벨

4

의 모든 엔트리는 왼쪽부터 ...