C++ STL의 priority_queue는 최대 힙(max heap)의 구현체입니다. 즉, 가장 큰 값이 항상 큐의 맨 앞(top)에 위치하며, 요소를 꺼낼 때마다 우선순위가 가장 높은(값이 가장 큰) 데이터부터 순서대로 반환됩니다.
이 글에서는 기본 자료형이 아닌 사용자 정의 구조체(structure)를 우선순위 큐에 저장하고, 특정 멤버 변수(예: 점수)를 기준으로 정렬하는 방법을 예제 코드와 함께 살펴보겠습니다.
알고리즘
구조체를 우선순위 큐와 함께 사용하는 전체적인 흐름은 다음과 같습니다.
시작
student 타입의 구조체를 정의한다.
student 구조체 내부 변수(학번, 점수)를 초기화한다.
comparemarks 타입의 또 다른 구조체를 정의한다.
comparemarks 구조체 안에서 student 구조체의
비교 연산자를 오버로딩한다.
해당 구조체와 함께 우선순위 큐를 선언한다.
student 구조체 형태로 큐에 여러 요소를 삽입한다.
큐가 빌 때까지 반복하며
요소를 하나씩 출력한다.
끝.예제 코드
아래 예제는 학생의 학번(roll)과 점수(marks)를 담는 student 구조체를 정의하고, 점수를 기준으로 내림차순 정렬되도록 comparemarks 구조체에서 함수 호출 연산자 operator()를 오버로딩한 코드입니다.
#include <iostream>
#include <queue>
using namespace std;
#define ROW 6
#define COL 3
struct student { // student 구조체 정의
int roll, marks;
student(int roll, int marks)
: roll(roll), marks(marks)
{
}
};
struct comparemarks { // comparemarks 구조체 정의
bool operator()(student const& s1, student const& s2)
// student 구조체의 비교 연산자 오버로딩
{
return s1.marks < s2.marks;
}
};
int main()
{
priority_queue<student, vector<student>, comparemarks> M;
// 우선순위 큐 사용. 구조체와 함께 사용할 때는 이러한 문법을 사용해야 한다.
int a[ROW][COL] = {{15, 50}, {16, 60},
{18, 70}, {14, 80}, {12, 90}, {20, 100}};
for (int i = 0; i < ROW; ++i) {
M.push(student(a[i][0], a[i][1])); // 큐에 요소 삽입
}
cout << "priority queue for structure ::" << endl;
while (!M.empty()) {
student s = M.top();
M.pop();
cout << s.roll << " " << s.marks << "\n"; // 값 출력
}
return 0;
}코드 설명
- student 구조체: 학번(
roll)과 점수(marks)를 멤버로 가지며, 생성자를 통해 값을 초기화합니다. - comparemarks 구조체:
operator()를 오버로딩하여 두 학생 객체를 비교합니다.s1.marks < s2.marks를 반환하므로 점수가 높은 학생이 더 높은 우선순위를 갖게 됩니다. - priority_queue 선언:
priority_queue<student, vector<student>, comparemarks>처럼 저장할 타입, 내부 컨테이너, 비교 기준 세 가지를 명시해야 구조체 기반 우선순위 큐를 사용할 수 있습니다.
실행 결과
priority queue for structure :: 20 100 12 90 14 80 18 70 16 60 15 50
실행 결과를 보면 입력 순서와 무관하게 점수가 가장 높은 학생(20번, 100점)부터 차례대로 출력됩니다. 이는 STL 우선순위 큐가 최대 힙으로 동작하기 때문이며, 비교 기준을 반대로 바꾸면(> 사용) 최소 힙처럼 동작하도록 만들 수도 있습니다.