삽입, 삭제 모두 O(logn)!! STL priority_queue 소개

priority_queue는 큐에 데이터가 삽입, 삭제 되어도 데이터들의 우선순위를 유지해주는 라이브러리이다.

priority_queue는 힙 구조로 구현되므로 삽입과 삭제의 시간 복잡도는 O(logn) 밖에 되지 않는다.

프로그래머라면 O(n)과 O(logn)의 차이가 얼마나 큰지 알고 있을 것이다. 후자는 거의 상수 취급 하기도 할 정도로 시간복잡도를 매우 단축할 수 있다.

 

힙 구조에 대한 자세한 설명은 아래 링크를 보면 좋다.

ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

priority_queue를 이용하여 본인이 푼 문제도 링크로 남겨두겠다.

kimcoder.tistory.com/102

[Heap, 난이도 중] 프로그래머즈, 이중우선순위큐

 

prioity_queue는 <queue> 헤더 파일에 있으며,

선언은 <자료형, 구현체, 연산자> 형태로 이루어진다.

priority_queue는 기본적으로 벡터 위에서 구현된다.

3번째 인자로 greater<int>를 넣으면 오름차순이 되며 작은 순서로 pop되고,

3번째 인자로 less<int>를 넣거나 생략하면 내림차순이 되며 큰 순서로 pop된다.

 

priority_queue를 사용하는 3가지 예제를 만들어 보았다.  

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int,vector<int>,greater<int> > pq1;
priority_queue<int,vector<int>,less<int> > pq2;
priority_queue<int> pq3;

int main(){
    pq1.push(3);
    pq1.push(2);
    pq1.push(6);
    pq1.push(1);
    pq1.push(4);
    pq1.push(8);
    while (!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    }
    cout << "\n";
    
    pq2.push(3);
    pq2.push(2);
    pq2.push(6);
    pq2.push(1);
    pq2.push(4);
    pq2.push(8);
    while (!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << "\n";
    
    pq3.push(3);
    pq3.push(2);
    pq3.push(6);
    pq3.push(1);
    pq3.push(4);
    pq3.push(8);
    while (!pq3.empty()) {
        cout << pq3.top() << " ";
        pq3.pop();
    }
    cout << "\n";
}

실행 결과

 

 

priority_queue에 구조체도 넣을 수 있는데, 연산자 오버로딩을 해줘야 한다.

아래 소스 코드는 구조체 (x,y) 쌍에서 x가 작은 쌍부터 출력해준다.

x,y를 랜덤으로 생성한 뒤, 10쌍을 pq에 push해주었다.

random_device에 대한 설명 -> kimcoder.tistory.com/133

 

#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
#include <random>
using namespace std;
struct node {
    int x;
    int y;
};

priority_queue<node> pq;

bool operator<(node a, node b) {
    return a.x > b.x;
}

int main() {
    random_device rd;
    for (int i = 0; i < 10; i++) {
    	pq.push({ rd() % 100 + 1,rd() % 100 + 1 });
    }
    while (!pq.empty()) {
    	cout << pq.top().x << ", " << pq.top().y << "\n";
    	pq.pop();
    }
}

실행 결과