※ 파이썬(Python) 유저의 경우 문제 하단의 힌트를 참고하면 된다. ※

priority_queue(우선순위큐)는 로그시간안에 삽입 및 가장 큰 원소의 추출을 제공하는 컨테이너 어댑터(container adaptor)다.

priority_queue는 기본적으로 앞서 배운 힙(heap), 그 중 최대힙(max heap)으로 구현이 되어있다.

최소힙(min heap)을 사용하고 싶다면 std::greater<T>를 사용하면 된다.

기본적인 함수로는 아래와 같은 함수들이 있다.

push(): 원소를 삽입한다

pop():top의 원소를 제거한다

top(): top에 있는 원소인 우선순위가 높은 원소를 반환한다

empty(): 비어있으면 true, 아니면 false를 반환한다

size(): 원소의 수를 반환한다

사용법은 아래와 같다.

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

int main()
{
    const auto data = {1,8,5,6,3,4,0,9,7,2};

    // 최대힙 선언 및 push함수로 원소 삽입
    priority_queue<int> max_heap;
    for(int n : data) max_heap.push(n);

    // 최소힙 및 초기화
    priority_queue<int, vector<int>, greater<int> > min_heap(data.begin(), data.end());

    // 힙 출력
    while(!max_heap.empty()){
        printf("%d ", max_heap.top());
        max_heap.pop();
    }
    printf("\n");

    while(!min_heap.empty()){
        printf("%d ", min_heap.top());
        min_heap.pop();
    }
    printf("\n");

    return 0;

}

priority_queue의 자료형은 변경이 가능하기에 구조체 또한 사용이 가능하다.

다만 구조체를 사용 할 때는 연산자 오버로딩을 통해 어떤 원소가 더 우선순위가 높은지 설정해줘야한다.

[문제]

정올 외과 응급실에서는 환자들을 입원시킬 때 환자의 나이와 출혈량을 물어본다.

출혈량이 높을 수록 더 먼저 수술을 받게 되는데, 출혈량이 같다면 고령의 환자를 먼저 수술한다.

환자의 입원과 수술 데이터를 실시간으로 처리하는 프로그램을 작성하라.

입원 데이터는 "push Thomas 37 120.6" 와 같이 이름, 나이, 출혈량(ml) 순서로 주어지며,

수술 데이터는 "pop"으로 주어진다. 이 경우 환자가 없다면 무시된다.

※ 구조체 연산자 오버로딩을 모른다면 참고: https://jungol.co.kr/problem/4641

#4905 upload 456 done 197 how_to_reg 178

STL - Priority Queue timer 1s memory 32MB

#4905

STL - Priority Queue 1s 32MB