[C++] STL priority_queue 정리 및 사용법

안녕하세요 기회개발자 기개 입니다.

오늘은 C++에서 사용하는 priority_queue에 대해 소개해보려고 합니다.

priority_queue를 직접 구현할 때에는 Heap을 사용하게 됩니다.

 

Heap이 무엇인지를 알아보고, heap으로 어떻게 priorty_queue를 구현하는지 알아보겠습니다.

그리고 STL 중 하나인 priority_queue의 사용법을 알아보도록 하겠습니다.

 

1. Heap이란

힙은 완전이진트리로 이뤄져 있습니다. 따라서 삽입(push)와 삭제(pop)을 할 때 O(nlogn)의 시간복잡도를 가지게 됩니다. 1) 최대힙과 최소힙 최대힙이란 가장 높은 값을 최상단 노드에 두고, push나 pop을 할 때마다 규칙에 따라 최상단 노드에 가장 높은 값을 올리는 것입니다. 최소힙은 최대힙과 반대로 가장 낮은 값을 최상단 노드에 두는 것입니다. 최대힙을 기준으로 push와 pop에 대해 알아보도록 하겠습니다. 2) push ① 트리의 가장 끝에 push하는 노드를 추가합니다. ② 부모노드와 비교를 하면서 자신보다 값이 작으면 자리를 바꿉니다. ③ ②를 반복하다가 부모노드가 자신보다 값이 크면 작업을 끝냅니다. 3) pop ① 가장 높은 값을 가진 최상단 노드를 반환합니다. ② 가장 끝에 있는 노드를 최상단 노드에 옮겨줍니다. (최상단 노드는 덮어쓰여져서 삭제됨) ③ 최상단 노드에서 부터 자식 노드들과 비교를 하면서 둘 중 값이 높은 것과 자리를 바꿉니다. ④ ③을 반복하다가 자신이 자식노드들보다 값이 크면 작업을 끝냅니다.

 

 

2. priority_queue를 Heap으로 구현?

최대힙, 최소힙의 개념을 보게 되면 조건(최댓값, 최솟값)에 따라 pop을 할 때 가장 먼저 나오게 합니다.

priority_queue를 생각해보면 조건을 사용자가 정한 우선순위(조건)에 따라 힙을 적용하면 된다는 것을 알 수 있게 됩니다.

 

 

3. priority_queue의 사용법 (내장함수)

priority_queue에는 데이터의 삽입, 삭제 등을 편하게 하기 위한 내장함수들이 존재합니다.

기본적으로 priority_queue를 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <queue>

using namespace std;

priority_queue<int> pq; // <>안에 삽입할 데이터의 자료형을 지정해줍니다.

 

1) 데이터의 삽입

데이터를 삽입할 때마다 앞서서 살펴본 heap의 규칙에 따라 삽입이 됩니다.

pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5); // 결과 {5, 4, 3, 2, 1}

 

2) 데이터의 삭제

최상단 노드를 삭제합니다.

pq.pop(); // 최상단에 있던 5가 삭제됩니다.

 

 

3) 데이터의 접근

priority_queue는 인덱스로 접근이 불가능합니다.

가장 최상단 노드에 어떤 값이 있는지만 알 수 있습니다.

pq.top() // 최상단 노드의 값인 4를 확인할 수 있다.

 

 

4) 이외에 유용한 내장함수

priority_queue에 데이터가 있는지, 몇 개의 데이터를 가지고 있는지를 알 수 있는 내장함수가 있습니다.

pq.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
pq.size(); // 데이터의 갯수 반환 | 결과 4

 

 

5) 응용

typedef struct st // 우선순위 정할 정보
{
    string word;
    int id;
}DATA;

struct compare // 부등호 방향이 set, map과 반대
{
	// id가 클수록 우선순위, id가 같다면 사전상 앞에 있을 경우 우선순위
    bool operator()(DATA a, DATA b) const{   
        if(a.id < b.id) return true; // id 내림차순(큰게 앞으로)
        else if(a.id == b.id && a.word > b.word) return true; // word 오름차순(작은게 앞으로)
        return false;
    }
};

// 선언, 직접 만든 비교 구조체(compare)을 넣을 경우 vector<{data_type}>을 중간에 넣어줘야 한다.
priority_queue<DATA, vector<DATA>, compare> pq;

DATA d1 = {"abc", 3};
DATA d2 = {"asdf", 2};

pq.push(d1);
pq.push(d2);

pq.top().word; // "asdf" 를 확인한다.
pq.pop(); // d2가 pq에서 삭제된다.

// 초기화 팁 (내장함수 clear() 없음)
while(!pq.empty()) pq.pop(); // 전부 꺼내주는 방법이 있지만 데이터 양이 많을 경우 오래 걸린다.

pq = {}; // 그냥 이렇게 해주면 초기화가 된다.