[알고리즘] 우선순위 큐 (최소힙, 최대힙)

soooprmx.com/archives/5121

우선순위 큐 혹은 최소/최대힙 · Wireframe

 

각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다.

 

 

간단히 생각해보면 priority queue는 리스트와 정렬함수를 쓰면 간단히 구현할 수 있을 것 같다. 하지만 리스트에 무언가를 삽입하는 것은 (리스트의 맨 뒤자리를 탐색해야 하므로) 

의 성능을 내고, 리스트를 정렬하는 것은 통상적인 좋은 정렬 알고리듬들이 그러하듯  

의 성능을 낸다.

 

 

 

하지만 실제로는 이보다 더 좋은 성능을 만들 수 있다. 바로 바이너리 힙(Binary Heap)이라는 자료 구조를 사용하는 것이다.

 

바이너리 힙은 매우 흥미로운 주제 중 하나인데, 트리형태의 자료를 단순히 하나의 리스트로만 구현하기 때문이다. 바이너리 힙은 두 가지 유형을 갖는데, 최소 값이 앞으로 오는 minHeap의 형태와 반대로 최대값이 앞으로 오는 maxHeap의 형태가 있다. 둘의 차이는 작은 값이 우선하느냐 큰 값이 우선하느냐의 차이만 있고 구현 방식은 동일하다.

 

 

 

 

우선순위 큐 혹은 최대최소 힙은 원소의 추가/삭제가 빈번한 상황에서 항상 리스트 내의 최소값 혹은 최대값을 기준으로 값을 꺼내어 쓰는 경우에 유용하다.

 

특히 이러한 경우는 다익스트라 알고리듬이나 A-Star알고리듬과 같이 리스트의 초기 상태 이후에 원소가 추가되더라도 늘 최소값/최대값 을 즉시 찾아내어야 하는 경우에 유리하게 사용할 수 있는 자료구조이다.

 

 

 

 

<구현방법>

 

오름차순 정렬 (최소힙) => 작은것부터 꺼내는 방식

 

 

 

내림차순 정렬 (최대힙) => 큰것부터 꺼내는 방식