STL 컨테이너 - priority_queue

priority_queue

**우선순위 큐(priority queue)**를 구현하는 C++ 표준 라이브러리의 컨테이너 어댑터입니다. 우선순위 큐는 큐와 유사하지만, 큐에 들어간 요소들이 삽입 순서가 아닌 우선순위에 따라 제거되는 특성을 가집니다. 즉, 우선순위가 높은 요소가 먼저 제거됩니다.

기본적으로 std::priority_queue는 최대 힙(max-heap)을 사용하여 가장 큰 요소를 우선순위가 높은 요소로 간주하고, 최소 힙(min-heap)을 사용하도록 설정을 변경할 수도 있습니다.

 

1. std::priority_queue의 특징

• 우선순위:
  • 기본적으로 큐에 삽입된 요소는 우선순위가 높은 순서대로 정렬됩니다. 기본 구현은 최대 힙(max-heap)을 사용하여, 가장 큰 값이 우선적으로 처리됩니다.
• 최대 힙 / 최소 힙:
  • std::priority_queue는 기본적으로 최대 힙을 사용하지만, 사용자 정의 비교 함수를 통해 최소 힙으로 동작하도록 할 수도 있습니다.
• 컨테이너 어댑터:
  • std::priority_queue는 내부적으로 다른 컨테이너(std::vector, std::deque 등)를 사용합니다.
  • 기본적으로 std::vector를 사용하지만, 다른 컨테이너로 변경할 수 있습니다.

2. 헤더 파일

std::priority_queue를 사용하려면 <queue> 헤더 파일을 포함해야 합니다.

 

3. 선언 및 초기화

최대 힙

최소 힙

사용자 정의 타입

4. std::priority_queue vs std::queue

접근 방식	FIFO (먼저 들어간 요소가 먼저 나옴)	우선순위가 높은 요소가 먼저 나옴
삽입	push() (맨 뒤에 추가)	push() (우선순위에 맞게 추가)
제거	pop() (맨 앞 제거)	pop() (가장 우선순위가 높은 요소 제거)
주요 용도	대기열 처리, 작업 스케줄링 등	우선순위가 중요한 작업 큐 처리, 알고리즘

 

5. std::priority_queue에서 사용할 수 있는 함수

push(val)	우선순위 큐에 요소를 추가합니다.
pop()	우선순위 큐에서 가장 우선순위가 높은 요소를 제거합니다.
top()	우선순위 큐에서 가장 우선순위가 높은 요소를 반환합니다.
empty()	큐가 비어 있으면 true, 아니면 false를 반환합니다.
size()	큐에 들어 있는 요소의 개수를 반환합니다.