우선순위 큐 (Prioirty Queue)

개념

우선순위 큐는 각 데이터에 우선순위를 부여하며 삽입 순서와 관계 없이 우선순위가 높은 데이터를 먼저 처리하는 자료구조이다. 우선순위가 동일하다면 이 때는 큐와 동일하게 선입선출 적용한다.

특징

• 우선순위 기반 처리 각 요소가 우선순위 값을 가지며, 가장 높거나 낮은 우선순위 요소를 먼저 처리한다.
• 자동 정렬 유지 데이터가 삽입될 때마다 내부적으로 정렬 상태를 유지하여, 우선순위가 가장 높거나 낮은 데이터에 빠르게 접근할 수 있다.
• 다양한 구현 방식 힙, 배열, 연결 리스트 등 다양한 자료 구조로 구현 가능하다.
• 높은 활용도 작업 스케줄링, 최단 경로 탐색 등 다양한 분야에서 활용할 수 있다.
• 효율적인 연산 (힙 기반 한정) 힙 기반일 경우 삽입/삭제 연산이 O(log n), 최대 또는 최솟값 조회에 O(1)의 시간 복잡도를 가진다.

장점

• 높은 유연성 Comparator 등 사용자가 우선순위 기준을 직접 정의할 수 있다.

단점

• 메모리 오버헤드 각 요소의 우선순위 정보를 추가로 저장해야하므로, 메모리 사용량이 증가할 수 있다.
• 구현 복잡성 일반적인 큐나 스택에 비해 구현이 복잡하며 유지 관리가 어렵다.
• 삽입/삭제 연산 오버헤드 (힙 기반 한정) 힙 기반일 경우 삽입/삭제 연산이 O(log n)의 시간 복잡도를 가져, 일반적인 큐의 시간 복잡도 O(1)보다 느리다.

std::priority_queue

priority_queue는 vector를 기반으로 구성된 컨테이너 어댑터로, 최대 또는 최소 원소에 빠르게 접근할 수 있다.