알고리즘 - 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

말 그대로 큐에 우선순위를 준 것을 의미한다. 큐의 경우 선입선출(FIFO First In First Out)의 규칙을 따르는데, 우선순위 큐는 큐에 우선순위를 부여하여, 우선순위가 높은 원소가 먼저 처리되는 구조를 갖는다.

우선순위 큐의 구조

일반적인 큐가 리스트와 같은 선형 자료 구조를 갖는 것에 비해 우선순위 큐는 트리 형태의 구조를 갖는다. 우선순위 큐는 최대힙(Max Heap)을 이용해 구현하는데 트리의 부모 노드가 자식 노드보다 큰 값을 갖는 구조이다.

우선순위 큐의 동작

삽입

원소 삽입 시 원소는 루트까지 거슬러 올라가며(상향식) 최대힙을 유지도록 구성된다.

삭제

원소 삭제는 루트 노드를 삭제 후 마지막 원소를 루트로 이동시긴다.
이후 하향식으로 최대힙을 유지하게 한다.