3.9 Priority Queue Ordering

개념

C++의 priority_queue에 구조체를 저장하면 여러 정보를 함께 보관하면서 꺼내는 순서를 정할 수 있습니다. 예를 들어 작업의 번호와 우선순위 값을 저장하고, 우선순위 값이 작은 작업부터 처리할 수 있습니다.

operator<로 우선순위 정의

priority_queue<T>의 기본 비교는 less<T>이며, 구조체에 정의한 operator<를 이용할 수 있습니다. a < b가 참이면 a를 b보다 낮은 우선순위로 취급합니다. 따라서 먼저 꺼낼 원소가 비교상 더 큰 원소가 되도록 정의합니다.

정수의 기본 <를 사용하면 가장 큰 수가 top()에 옵니다. 작은 우선순위 값부터 꺼내려면 비교 연산자에서는 반대로 큰 값을 낮은 우선순위로 취급해야 합니다.

우선순위 값이 $5$인 작업과 $2$인 작업 중 $2$를 먼저 꺼내려면, $5$인 작업을 왼쪽에 놓고 비교했을 때 참을 반환해야 합니다. 그래서 비교식은 $5>2$입니다.

여러 기준과 멤버 함수 문법

작업의 우선순위 값을 먼저 비교하고, 같을 때만 번호를 비교합니다. (번호, 우선순위 값)이 $(3,2)$, $(1,2)$, $(2,1)$이면 처리 순서는 번호 $2$, $1$, $3$입니다.

멤버 함수의 형태는 bool operator<(const Job& a) const입니다. x < y를 계산할 때 함수 안의 p, id는 왼쪽 원소 x의 값이고, 매개변수 a는 오른쪽 원소 y입니다. 매개변수의 const는 비교 대상의 변경을 막고, 함수 끝의 const는 왼쪽 원소를 변경하지 않는다는 뜻입니다. 반환형 bool은 비교 결과가 참 또는 거짓임을 나타냅니다.

같은 operator<를 사용하는 정렬과 우선순위 큐는 결과를 읽는 방향이 다릅니다. 오름차순 정렬은 비교상 앞선 원소부터 나열하지만, 기본 우선순위 큐는 비교상 가장 큰 원소부터 꺼냅니다. 별도 비교 객체를 세 번째 템플릿 인자로 전달한 큐는 그 객체의 기준을 사용합니다.

비교 연산자의 유의점

비교 기준은 엄격 약순서를 만족해야 합니다. 다음 조건을 확인하면 잘못된 비교식을 찾는 데 도움이 됩니다.

• 같은 원소끼리 비교한 a < a는 거짓이어야 합니다. <=나 >=를 쓰면 같은 값에서도 참이 될 수 있습니다.
• a < b와 b < a가 동시에 참이 되어서는 안 됩니다.
• a < b이고 b < c이면 a < c여야 합니다.
• 서로 앞서지 않는 원소들을 같은 우선순위로 취급할 때도 그 관계가 일관되어야 합니다.

이 요구사항은 C++ 표준 초안의 priority_queue 정의에 명시되어 있습니다.

동점 기준을 정하지 않으면 같은 우선순위의 원소가 입력 순서대로 나온다는 보장은 없습니다. 입력 순서대로 처리해야 한다면 삽입 순번을 함께 저장하여 동점 기준으로 비교합니다.

큐에 저장한 뒤 비교에 쓰는 값을 외부에서 바꾸면 내부 힙의 순서가 자동으로 다시 정리되지 않습니다. 변경한 작업을 새 원소로 넣고, 이전 항목은 꺼낼 때 최신 상태와 비교하여 처리하는 방법을 사용할 수 있습니다. 일반 값으로 저장한 구조체는 복사되어 들어가므로 원본 변수의 값을 바꾸어도 큐 안의 복사본은 바뀌지 않습니다.

top()은 상수 참조를 반환합니다. 원소를 사용할 때는 top()으로 값을 복사한 뒤 pop()으로 제거합니다. pop() 자체는 제거한 값을 반환하지 않습니다.

복잡도

큐에 든 원소 수를 $N$이라고 합니다. 비교할 정수 필드 수가 고정되어 있으므로 한 번의 비교는 $O(1)$입니다.

예제

문제

작업들을 우선순위 값이 작은 순서대로 처리하여라. 우선순위 값이 같으면 번호가 작은 작업을 먼저 처리한다.

입력

첫째 줄에 작업 수 $N$이 주어진다. $1\le N\le100$이다.

다음 $N$개 줄에 작업 번호 $i$와 우선순위 값 $p$가 공백을 사이에 두고 주어진다. $1\le i,p\le1\,000$이며, 작업 번호는 서로 다르다.

출력

작업 번호를 처리 순서대로 한 줄에 공백으로 구분하여 출력한다.