[C++] priority_queue 사용법

© Copyright 2020 Standard C++ Foundation. All rights reserved.

[C++] priority_queue 사용법

(글쓴날 : 2020.04.26)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

---

 

 

C++ priority_queue 사용법

---

1) priority_queue란?

priority_queue란 자료구조 queue의 일종으로 <queue> 헤더에 존재합니다.

priority_queue는 queue와 똑같이 추가(push), 삭제(pop) 등의 기능을 하며, 일반 queue와 달리 우선순위를 기준으로 수행하는 것이 특징입니다.

보통, 우선순위를 선정하기 위해 내부적으로 heap 자료구조를 사용하며, 그에 따라 추가(push) 및 삭제(pop) 시 O(log n)의 시간 복잡도가 걸리게 됩니다.

 

또한, 우선순위 설정을 위해 보통 <functional> 헤더의 greater<>, less<> STL을 사용하며, 만약, 사용자 정의 우선순위 설정이 필요하다면 operator()를 추가로 구현하여 사용합니다.

(아무 우선순위도 설정하지 않을 시, 내림차순(MaxHeap) 우선순위로 설정됩니다.)

---

2) priority_queue 사용법

(1) <queue> 헤더 include 및 표준 네임스페이스 사용 선언

#include <queue>
using namespace std;

---

(2) priority_queue 생성(기본)

기본 생성 방법은

priority_queue<(type)> 이름;

입니다.

(기본으로 생성할 시, 내림차순(Max Heap)으로 구현됩니다.)

ex)

priority_queue<int> pq1;

---

(3) Priority_queue 생성(우선순위 설정)

우선순위 설정 방법은

priority_queue<(type), vector<(type)>, (우선순위 기준)> 이름;

이며,

기본 생성 제네릭 매개변수에 vector<(type)>, (우선순위 기준) 두 가지 인자를 추가로 overload 해주면 됩니다.

이 예시에서는, 오름차순(Min Heap) 우선순위 구현을 위해 <functional> 헤더의 greater<>를 우선순위 기준으로 사용했습니다.

ex)

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

---

(4) .push(), .size() : 값 추가(push) 및 사이즈(size) 확인

일반적인 queue와 마찬가지로 push() 함수를 이용해 값을 추가해 주시고, size() 함수를 이용해 사이즈를 확인해 주시면 됩니다.

ex)

// priority_queue<int> pq1; (내림차순)
pq1.push(1);
cout << pq1.size() << endl;    // cout결과 : 1
pq1.push(2);
cout << pq1.size() << endl;    // cout결과 : 2
pq1.push(3);
cout << pq1.size() << endl;    // cout결과 : 3
 
// priority_queue<int, vector<int>, greater<int>> pq2; (오름차순)
pq2.push(1);
cout << pq2.size() << endl;    // cout결과 : 1
pq2.push(2);
cout << pq2.size() << endl;    // cout결과 : 2
pq2.push(3);
cout << pq2.size() << endl;    // cout결과 : 3

---

(5) .top(), .pop() : 우선순위가 제일 높은 값 확인(top) 및 삭제(pop)

일반적인 큐와 마찬가지로 top() 함수와 pop() 함수를 사용해 주시면 되지만, priority_queue의 경우 저장되어 있는 값 중 설정한 우선순위가 제일 높은 순으로 수행됩니다.

ex)

// priority_queue<int> pq1; (내림차순)
cout << pq1.top() << endl;    // cout결과 : 3
pq1.pop();
cout << pq1.top() << endl;    // cout결과 : 2
pq1.pop();
cout << pq1.top() << endl;    // cout결과 : 1
pq1.pop();
 
// priority_queue<int, vector<int>, greater<int>> pq2; (오름차순)
cout << pq2.top() << endl;    // cout결과 : 1
pq2.pop();
cout << pq2.top() << endl;    // cout결과 : 2
pq2.pop();
cout << pq2.top() << endl;    // cout결과 : 3
pq2.pop();

---

(6) .empty() : 우선순위 큐가 비어있는지 확인

마찬가지로, 일반적인 큐처럼 empty() 함수를 사용해 주시면 되겠습니다.

ex)

cout << pq1.empty() << endl;  // cout결과 : 1(true)
 
pq2.push(1);
cout << pq2.empty() << endl;  // cout결과 : 0(false)

---

(7) 사용자 정의 우선순위 설정

사용자 정의 우선순위 설정은 operater()를 추가로 구현하여, 연산자 오버로딩을 통해 설정합니다.

operater() 인자의 첫 번째에 비교할 기존 값, 두 번째에 새로 추가할 값을 지정하여 원하는 우선순위가 true를 반환하도록 재정의 해주시면 됩니다.

다음은, 오름차순(Min Heap) 우선순위를 설정하는 예시입니다.

ex)

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct prio {
    bool operator()(int oldValue, int newValue) {
        return oldValue > newValue;
    }
};
 
int main(void) {
    priority_queue<int, vector<int>, prio> pq3;
 
    pq3.push(3);
    pq3.push(2);
    pq3.push(1);
 
    cout << pq3.top() << endl;    // cout결과 : 1
    pq3.pop();
    cout << pq3.top() << endl;    // cout결과 : 2
    pq3.pop();
    cout << pq3.top() << endl;    // cout결과 : 3
    pq3.pop();
 
    return 0;
}

---

 

 

---

 

 

여기까지, C++의 priority_queue 사용법에 대하여 알아봤습니다.

감사합니다!