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

121

4

장

힙

이 장에서 배울 내용은 다음과 같다.

●

큐와 우선순위 큐 데이터 타입

●

1964

년에 개발된, 배열에 저장 가능한 이진 힙 자료구조

●

최대 이진 힙에서 엔트리의 우선순위 수가 클수록 우선순위가 더 높다고 간주된다.

●

(값, 우선순위 ) 엔트리를 이진 힙에

O

(

log

N

) 복잡도로 넣는 방법 (

N

은 힙 내 엔트리 개수 )

●

이진 힙에서 우선순위가 가장 높은 값을

O

(

1

) 복잡도로 찾는 방법

●

이진 힙에서 우선순위가 가장 높은 값을

O

(

log

N

) 복잡도로 제거하는 방법

단지 값의 컬렉션을 저장하는 대신에, 각 엔트리에 값과 숫자로 표시된 연관된 우선순위가 있

는 엔트리 모음을 저장하면 어떻게 될까? 두 엔트리가 주어졌을 때 하나는 우선순위가 높아 다

른 것보다 더 중요하다. 이번에는 컬렉션에 새로운 (값, 우선순위 ) 엔트리를 넣고 제거할 수

있으며 컬렉션에서 우선순위가 가장 높은 엔트리에 대한 값을 반환받을 수 있도록 하자.

이런 동작은

우선순위 큐

priority

queue

를 정의한다. 우선순위 큐는

enqueue

(

value

,

priority

)

와 우선순위가 가장 높은 값을 제거하는

dequeue

()

를 효율적으로 지원하는 데이터 타입이다.

우선순위가 가장 높은 값을 제거하기 위해 요청할 때 미리 우선순위를 알 필요가 없으므로 이

전 장에서 ...