우선 순위 큐 (Priority Queue)

우선 순위 큐는 큐나 스택과 비슷한 축약 자료형이다.

예를 들면 일반적인 큐는 선입 선출의 특성이 있고 스택은 후입 선출의 특성이 있다.

 

또한 우선 순위 큐는 힙이라고 생각을 하는데 이는 오류이다.

우선 순위 큐를 구현하는 방식에 따라 다양한 방법으로 구현 가능하다.

 

우선 순위 큐를 배열이나 연결리스트로 구현하지 않는 이유는 아래와 같다.

1. 배열로 구현한 경우

우선 순위가 중간인 데이터가 삽입되는 경우 데이터가 삽입되는 위치 부터 모든 데이터를 한칸씩 뒤로 미뤄야하는 문제가 발생하며 시간 복잡도(time complexity)가 O(n)이다.

 

2. 연결리스트로 구현한 경우

우선 순위가 중간이 데이터가 삽입되는 경우 데이터가 들어갈 위치를 탐색해야하는데 O(n)만큼 걸린다.

 

3. 힙으로 구현한 경우

힙은 완전 이진 트리(Complete Binary Tree)이므로 데이터 삽입 시 시간 복잡도는 O(long2n)이다.

 

배열이나 연결리스트로 구현을 하지 않고 힙으로 구현하는 이유는 시간 복잡도를 줄이기 위함이다.

 

c++ STL에서는 priority_queue를 지원한다.

priorty_queue를 통해 손쉽게 Max Heap과 Min Heap을 구현 할 수 있다.

Max Heap : 부모 노드는 항상 자식 노드에 들어 있는 값 보다 크다 (부모 >= 자녀)

Min Heap : 부모 노드는 항상 자식 노드에 들어 있는 값 보다 작다 (부모 <= 자녀)

 

Max Heap의 경우 Priority_queue 생성 시 class Compare를 less로 설정한다.

Min Heap의 경우 Priorty_queue 생성 시 class Compare를 greater로 설정한다.

 

Max Heap Example

Max Heap Example Result

Min Heap Example

Min Heap Example Result

참고 자료 1 : ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

우선순위 큐 - 위키백과, 우리 모두의 백과사전

참고 자료 2 : docs.microsoft.com/ko-kr/cpp/standard-library/priority-queue-class?view=msvc-160

priority_queue 클래스