(C++) 우선순위 큐(Priority Queue)

우선순위 큐란?

우선순위를 가지는 데이터들을 저장하는 큐(Queue)를 말한다.
데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다.

 

우리가 흔히 말하는 큐(Queue)와의 차이는 일반적인 큐는 아래 그림과 같이 선형적인 구조를 가지는 반면 우선순위 큐는 트리 구조로 생각할 수 있다.

우선순위 큐의 동작 원리

일반적으로 우선순위 큐는 최대 힙(Max Heap)을 이용해 구현한다. 그래서 우선순위 큐의 동작 원리를 알아보기 전에 먼저 최대 힙에 대해 알아보자.

 

최대 힙은 부모 노드가 자식 노드 보다 값이 큰 완전 이진트리를 의미한다. 그렇기에 루트 노드는 전체 트리에서 가장 큰 값을 가진다.

이제 우선순위 큐의 동작 원리를 알아보자.

 

1. 우선순위 큐의 삽입(PUSH)

• 삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입
• 삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성(상향식)

2) 우선순위 큐의 삭제(POP)

• 삭제할 때는 루트 노드를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 이동
• 삭제 후 리프 토드까지 내려가면서 최대 힙을 구성(하향식)

우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다. 따라서 우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다.

 

우선순위 큐 사용

우선순위 큐는 다음과 같이 STL queue를 include 하여 사용한다. 그렇기 때문에 queue와 사용법이 거의 비슷하다.

#include <queue>

그 후 아래와 같이 선언하면 우선순위 큐를 사용할 수 있다.

priority_queue<타입명> 변수명;

사용할 수 있는 멤버 함수는 다음과 같다.

• empty : 우선순위 큐가 비었는지 확인 후 비었으면 1을 아니면 0을 반환한다.
• size : 우선순위 큐의 크기를 반환한다.
• top : 우선순위 큐의 최우선 값을 반환한다.
• push : 우선순위 큐에 값을 삽입한다.
• emplace : 우선순위 큐에 구조체를 삽입한다.
• pop : 우선순위 큐의 최우선 값을 제거한다.
• swap : 우선순위 내의 두 값을 바꾼다.

이들을 사용한 간단한 예시를 확인해보자.

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

int main() {
  // 우선순위 큐 선언
  priority_queue<int> pq;

  // 우선순위 큐에 값을 넣는다.
  pq.push(1);
  pq.push(2);
  pq.push(3);
  pq.push(4);
  pq.push(5);

  // 출력결과 : 5
  cout << pq.size() << endl;

  // 우선순위 큐 출력
  while(!pq.empty()) { // 큐가 빌 때까지 반복
    int temp = pq.top(); // 큐 내의 최우선 값 가져오기
    cout << temp;
    pq.pop(); // 큐의 최우선 값 삭제
  }

  /* 출력결과
  54321 */
  return 0;
}

 

출처

🌈 자료구조:: 우선순위 큐(Priority Queue)

 

C++ STL priority_queue 우선순위 큐 사용법