우선순위 큐

C++에는 우선순위 큐(priority queue)라고 불리는 데이터 구조도 있습니다. 우선순위 큐는 일반 큐에는 없는 특별한 기능을 제공하는데, 각 요소가 우선순위 값과 연결되어 있으며 요소들이 우선순위에 따라 처리되는 방식입니다.

기본적인 우선순위 큐는 큐의 첫 번째 요소가 모든 요소 중 가장 크고, 나머지는 내림차순으로 정렬되도록 설계되어 있습니다.

priority_queue<dataType> queueName

먼저, C++ 파일 상단에 priority queue 헤더 파일을 포함해야 합니다.

이미 배운 다른 컨테이너들과 마찬가지 방식으로 우선순위 큐를 생성합니다.

priority_queue<int> integers;

다음으로, push() 메서드를 사용하여 큐에 새로운 요소를 추가합니다. 요소가 추가될 때, 만약 그것이 모든 요소보다 크다면 첫 번째에 저장됩니다. 다른 모든 요소보다 작다면 마지막에 저장되는 식입니다.

integers.push(5);  // integers = {5)

요소를 출력하기 위해서는 스택과 마찬가지로 top() 메서드를 사용합니다. 이는 우선순위가 가장 높은 요소를 출력하며, 정수의 경우에는 가장 큰 숫자를 출력합니다.

integers.push(100);  // integers = {100, 5}
integers.push(10);  // integers = {100, 10, 5}
integers.push(3);  // integers = {100, 10, 5, 3}
cout << integers.top();

Output:
100

요소를 제거할 때도 스택과 똑같이 pop() 메서드를 사용합니다. 이는 맨 위에 있는 요소, 즉 우선순위가 가장 높은 요소를 제거합니다. 숫자의 경우에는 가장 큰 숫자가 제거됩니다.

integers.pop();  // integers = {10, 5, 3}
cout << integers.top();

Output:
10

요소들이 정렬되는 기준인 큐의 우선순위를 변경할 수 있습니다. 예를 들어, 아래와 같이 정수를 오름차순으로 정렬하는 우선순위 큐를 선언할 수 있습니다.

priority_queue<int, vector<int>, greater<int> > integers;

이 큐에서는 요소가 삽입될 때 오름차순으로 정렬됩니다. top() 메서드를 사용하여 맨 위 요소를 표시하거나 pop() 메서드를 사용하여 제거할 때, 가장 작은 숫자가 표시되거나 제거됩니다.

지금은 우선순위 큐를 다른 방식으로 사용하거나 우선순위를 변경하는 것에 대해 너무 고민하지 마세요. 단지 이 데이터 구조를 사용하여 어떤 종류의 우선순위에 따라 요소를 정렬할 수 있다는 점만 기억해 두세요.

우선순위 큐 메서드