[C++] Priority Queue 사용하기

알고리즘 문제를 풀다보면 생각보다 Priority Queue를 많이 사용해야한다..
흐린 눈 하고 다른 문제 풀려다가 이참에 정리하는 Priority Queue 사용법 정리

1. 헤더파일

C++ 기준으로 Priority Queue는 queue 헤더파일에 같이 선언되어있다.

#include <queue> 

2. 내장함수

• empty : 큐가 비었는지 확인하는 함수
• size : 큐의 사이즈 확인 (내부에 들어있는 원소의 개수 확인)
• top : 큐의 최상위원소 확인 - 최상위 원소를 return 한다
  
• push : 큐에 삽입
• pop : 큐의 최상위원소 제거

예제 코드

#include <iostream>
#include <queue> // priority_queue는 queue 헤더파일에 선언되어있다 
// 이건 난수발생을 위한 헤더파일들! 
#include <stdlib.h>
#include <time.h>

using namespace std;

void queue_push(int N);
void queue_pop();

priority_queue<int> Q;

int main() {
	//time.h 헤더파일을 이용해서 
	srand(time(NULL));
	queue_push(5);
	queue_pop();
	return 0;
}

void queue_push(int N) {
	for (int i = 0; i < N; ++i) {
		//난수 생성 rand 함수와 100 까지의 난수만 발생시키기 위해 100으로 나눈 나머지 값을 저장
		int N = rand() % 100;
		Q.push(N);
		cout << "input : " << N << '\n';
	}
	return;
}
void queue_pop() {
	cout << "----------------\n";
	cout << "Q 사이즈 : " << Q.size() << '\n';
	cout << "----------------\n";
	while (!Q.empty()) {
		cout << "output : " << Q.top() << '\n';
		Q.pop();
	}
	return;
}

결과

3. 심화편

• swap : 두 prioirty_queue 객체의 내부 데이터 구조를 교환한다 -> 객체의 포인터만 교환되기 때문에 얕은 복사가 수행된다고 볼 수 있음 !
• emplace : 객체를 직접 생성해서 삽입한다 <-> push의 경우 따로 새로운 객체를 생성한 뒤 삽입한다
  - 메모리 할당과 복사 작업을 줄일 수 있다

// push 사용
    pq.push(MyClass(1, 2));
    pq.push(MyClass(3, 4));

    // emplace 사용
    pq.emplace(5, 6);
    pq.emplace(7, 8);

예제코드

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq1, pq2;

    cout << "input \n";
    cout << "pq1 : 10 5 15 \n";
    // pq1에 요소 추가
    pq1.emplace(10);
    pq1.emplace(5);
    pq1.emplace(15);

    cout << "pq2 : 40 25 30 \n";
    // pq2에 요소 추가
    pq2.emplace(40);
    pq2.emplace(25);
    pq2.emplace(30);

    // pq1과 pq2 swap
    pq1.swap(pq2);

    // 각 큐 출력
    cout << "output \n";
    cout << "pq1: ";
    while (!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    }
    cout << '\n';
    cout << "pq2: ";
    while (!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << '\n';

    return 0;
}

결과

4. 우선순위큐의 구조

우선순위 큐의 내부는 완전이진트리 힙(heap) 자료구조를 사용해서 정렬된다.

완전이진트리(Complete Binary Tree) ?

각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져있는 노드
또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입된다

• 삽입
• 삭제
  다음과 같이 삽입 / 삭제의 경우 최대 시간 복잡도가 log(n)이다.