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

145

4

장

힙

dequeue

()

로직이 맞다는 확신을 얻으려면 엔트리를 한 개만 포함하는 힙에서 해당 로직이 동

작하는 방식을 살펴보자. 엔트리가 한 개인 힙에서

dequeue

()

를 하면

max

_

entry

의 값을 반

환받을 것이고

sink

()

를 호출하기 전에

N

이

0

이 되므로,

sink

()

의

while

루프의 조건에서

2

×

1

>

0

이 되어 아무것도 하지 않을 것이다.

4.6

요약

이진 힙 구조는 우선순위 큐 추상 데이터 타입의 효율적인 구현을 제공한다.

7

장에서 논의할

여러 알고리즘은 우선순위 큐에 의존한다.

●

(값, 우선순위 ) 엔트리의

enqueue()

수행은 성능이

O

(

log

N

)이다.

●

우선순위가 가장 높은 엔트리의

dequeue()

수행은 성능이

O

(

log

N

)이다.

●

힙의 총 엔트리 수를 얻는 성능은

O

(

1

)이다.

이번 장에서는 최대 이진 힙에 대해서만 학습했다.

최소 이진 힙

min

binary

heap

을 실현하려면 더

작은 우선순위 값을 가지는 엔트리가 더 높은 우선순위를 가지도록 약간만 변경하면 된다. 이

는

7

장과 연관이 있다. [코드

4

-

2

]에서 미만(

<

) 대신에 초과(

>

)를 사용해

less

()

메서드를

재작성하면 된다. 이외의 코드는 모두 동일하다.

def less(self, i, j):

return self.storage[i].priority ...