C++ Priority queue 컨테이너 사용법

병원에서의 우선순위 큐

c++에서의 priority_queue는 c++에서 vector와 같은 컨테이너의 한 종류이며 우선순위 큐를 사용한다면 큐에 있는 모든 원소들이 가장 우선순위가 큰 값이 Top을 유지하도록 설계되어 있다.

우선순위 큐는 Heap이라는 자료구조를 사용하고 있다.

 

Heap

 

힙 자료구조는 완전이진트리를 기초라 하는 자료구조이다. 완전이진트리는 마지막을 제외한 모든 노드가 자식들이 있는 것을 의미한다.

 

힙은 크게 1)최대힙 , 2)최소힙으로 나뉘어진다.

최소힙과 최대힙

최대힙은 각 노드의 키값이 (자식노드가 존재한다면) 항상 자식노드의 키값보다 크거나 같은 자료구조이다.+

완전이진트리

 

최소힙은 각 노드의 키값이(자식노드가 존재한다면) 항상 자식노드의 키값보다 작거나 같은 자료구조이다. +

완전이진트리

---

Priority_queue의 생성

In order to create a priority queue in C++, we first need to include the queue header file.

#include <queue>

 먼저 헤더파일에 #include <queue>를 넣어주자.

 

 

Once we import this file, we can create a priority_queue using the following syntax:

priority_queue<type> pq;

헤더파일을 넣어줬다면

priority_queue<데이터타입> 이름

ex_ ) priority_queue<int> myqueue

 

Note: By default, STL priority_queue gives the largest element the highest priority.

 

기본설정으로 STL prioirty_queue는 원소가 큰 값이 우선순위가 크도록 되어있다

---

Priority_queue 메소드

MethodsDescription

push()	inserts the element into the priority queue
pop()	removes the element with the highest priority
top()	returns the element with the highest priority
size()	returns the number of elements
empty()	returns true if the priority_queue is empty

push()->우선순위큐에 요소를 삽입합니다.

pop()->우선순위가 높은 요소를 제거합니다.

top()->우선순위가 가장 높은 요소를 반환해줍니다.

size()->우선순위 큐의 크기를 반환합니다.

empty()->우선순위 큐가 비어있는지 여부를 반환해줍니다.

 

 

우선순위 큐를 사용한 예시 코드 ->

백준 최대힙 11279번

 

#include <iostream>

#include <queue>

using namespace std;

int main(void){

    ios_base :: sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

   

    priority_queue<int> q;  //우선순위 큐의 선언 ->default로 큰 값이 우선순위가 크다.

   

    int n;

    cin >> n;

    for(int i = 0;i<n;i++){

        int element;

        cin >> element;

        if(element != 0){

            q.push(element); //push연산

        }

        else if(element == 0){

            if(q.empty()){ //q.empty() -> 큐가 비어있는지 여부

                cout << '0' << '\n';

            }

            else{

            cout << q.top() << '\n'; //top()->우선순위가 가장 큰 값 리턴

            q.pop(); //pop연산

            }

        }

    }

   

}

---