[자료구조] 우선순위큐(Priority Queue)

우선순위큐(Priority Queue) 란?

우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 된다.

 

응용분야

- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영체제에서의 작업 스케줄링

 

우선순위큐 STL 기본 형태

priority_queue<T,Container,Compare> : 원하는 자료형 및 클래스 T를 통해 생성, 여기서 Container는 Vector와 같은 컨테이너 이며 Compare 는 비교 함수 클래스(단,Compare 조건에서 참인 것이 후 순위로 밀린다.)

 

우선순위큐 함수

push(element) : 우선순위 큐에 추가
pop() : 원소 삭제
top() : top에 있는 원소를 반환
empty() : 비어있으면 true 아니면 false
size() : 우선 순위 큐에 포함되어 있는 원소들의 수를 반환

 

우선순위큐 구현 예

 

struct INT{
    public :
        int a;
        INT(){};
        INT(int x){a=x;};
};
struct cmp{
    bool operator()(INT a,INT b)
    {
        return a.a < b.a;
    }
} ;
 
int main()
{
    priority_queue<INT,vector<INT>,cmp>pq;
    pq.push(INT(2));
    pq.push(INT(5));
    pq.push(INT(8));
    while(!pq.empty())
    {
        INT imsi = pq.top();
        cout << imsi.a << endl;
        pq.pop();
    }
    return 0;
}
 

 

struct INT{
    public :
    int a;
    INT(){};
    INT(int x){a=x;};
};
 
bool operator<(INT a,INT b)
{
        return a.a < b.a;
}
 
int main()
{
    priority_queue<INT>pq;
    pq.push(INT(2));
    pq.push(INT(5));
    pq.push(INT(8));
    while(!pq.empty())
    {
        INT imsi = pq.top();
        cout << imsi.a << endl;
        pq.pop();
    }
    return 0;
}
 
 

문제풀이

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2630&sca=9010

JUNGOL

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
 
using namespace std;
 
typedef struct info
{
    int id;
    int w; //시간
    int num; //계산대번호
    bool operator < (const info &r) const{
        if(w>r.w)return true;
        else if(w==r.w)
        {
            if(num<r.num)return true; //계산대 번호가 큰걸 뽑자
        }
        return false;
    }
}info;
 
priority_queue <info> pq1;//outq
 
typedef struct data
{
    int id;
    int t;
    int num;
    bool operator < (const data &r) const{
        if(t>r.t)return true;
        else if(t==r.t)
        {
            if(num>r.num)return true; //계산대 번호가 작은걸 뽑자.
        }
        return false;
    }
}data;
 
priority_queue <data> pq2;//inq
 
int main()
{
    //freopen("input.txt","r",stdin);
    int n,k,i;
    int a,b;
    scanf("%d %d",&n,&k);
    data tmp;
    info imsi;
 
    for(i = 0;i < n;i++)
    {
 
        scanf("%d %d",&a,&b);
        if(i<k)
        {
            tmp.num = i+1;
            tmp.t = b;
            tmp.id = a;
           // pq2.pop();
            pq2.push(tmp);
 
            imsi.id = a;
            imsi.num = tmp.num;
            imsi.w = b;
            pq1.push(imsi);
        }
        else
        {
            tmp = pq2.top();
            pq2.pop();
 
            tmp.id = a;
            tmp.t += b;
 
            imsi.id = tmp.id;
            imsi.num = tmp.num;
            imsi.w = tmp.t;
            pq1.push(imsi);
            //printf("(%d,%d,%d)\n",imsi.id,imsi.num,imsi.w);
 
            pq2.push(tmp);
        }
 
    }
    int ind=1;
    long long int sum=0;
    while(!pq1.empty())
    {
        sum += (long long)ind*pq1.top().id;
        //printf("%d\n",pq1.front().id);
        ind++;
        pq1.pop();
    }
    printf("%lld",sum);
    return 0;
}