우선순위 큐

개념

우선순위 큐란 우선순위가 높은 데이터를 먼저 꺼내는 자료구조이다.

우선순위 큐는 보통 힙으로 구현한다. 힙은 Max heap, Min heap이 있는데, Max heap은 부모노드가 자식노드보다 큰 힙이고, Min heap은 부모노드가 자식노드보다 작은 힙이다.

따라서 오름차순으로 정렬할 경우에는 Min heap을, 내림차순으로 정렬할 경우에는 Max heap을 사용한다. 

c++에서는 <queue> 헤더파일을 이용하여 우선순위 큐를 간단하게 구현할 수 있다.

 

구현 (queue 헤더파일 사용 x)

- heap에 데이터 추가

void addToHeap(int v, int last)
{
    int cur = last +1;
    int parent = cur/2;
    arr[cur] = v;

    while(1)
    {
        if(arr[parent]>arr[cur])
        {
            return;
        }
        else
        {
            myswap(parent, cur);
            cur=parent;
            parent=cur/2;
            if(parent<1) return;
        }
    }
}

- heapify(Max heap으로 만들기)

void heapify(int last)
{
    int cur_idx = last/2;
    while(cur_idx>=1)
    {
        findlocation(cur_idx,last);
        cur_idx--;
    }
}

- Max heap으로 만들기 위해 노드들이 위치할 자리 찾기

void findlocation(int cur, int last)
{
    int leftidx = cur*2;
    int rightidx = leftidx+1;
    int biggest = cur;

    if(leftidx<=last && arr[leftidx]>arr[cur])
    {
        biggest = leftidx;
    }
    if(rightidx<=last && arr[rightidx]>arr[biggest])
    {
        biggest = rightidx;
    }
    if(biggest==cur) return;
    else //cur idx가 자기자리로 가도록 biggest 와 자리 교체
    {
        myswap(cur,biggest);
        findlocation(biggest,last);
    }
}

- myswap (인덱스를 가지고 전역변수로 선언된 배열의 값 서로 바꾸기)

void myswap(int a, int b)
{
    int tmp = arr[b];
    arr[b]=arr[a];
    arr[a]=tmp;
}

- Root 삭제

int removeRoot(int last)
{
    int ret = arr[1];
    arr[1]= arr[last];
    findlocation(1,last-1);
    return ret;
}

- main 함수

//전역변수로 arr이 int arr[lastIdx+1] = {0,6,3,5,7,10,1,2};로 선언됨

int main()
{
    int k;
    cout<<arr[1]<<endl; //6(힙으로 만들기 전 루트)
    heapify(7);
    cout<<arr[1]<<endl; //10(Max heap이므로 가장 큰 수가 루트)
    addToHeap(30,7);
    cout<<arr[1]<<endl; //30(10보다 큰 30이 추가되었으므로)
    addToHeap(40,8);
    cout<<arr[1]<<endl; //40(30보다 큰 40이 추가되었으므로)
    k=removeRoot(8);
    cout<<arr[1]<<endl; //30(루트에 있던 40이 제거됨)
}

 

예제 https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

풀이 

위에서 구현한 것과 같이 우선순위 큐를 구현하여 해결했다. 배열을 이용했는데, 인덱스 계산을 위해 배열의 첫 번째 요소는 0으로 설정하고 사용하지 않는다.

 

그런데 이 문제에서는 음수도 들어오는데, 만약 음수가 첫 번째 입력으로 주어지면, 배열의 첫 번째 요소인 0과 비교해서 뒤로 밀어버렸다. 따라서 그 경우는 따로 예외 처리를 해줬다. addToHeap 함수에서 last가 1이고, 값이 0보다 작은 경우에는 배열의 두번째 자리에 값을 넣고 리턴시켰다.

 

그렇게 값을 다 입력 받고, Max Heap으로 만든 후에 n까지 돌면서 루트를 제거했다. 루트에는 항상 최대값이 들어있기 때문에 n만큼 반복해주면 n번째로 큰 수를 출력할 수 있다.

 

코드

#include <iostream>
using namespace std;

int arr[1510*1510];

void myswap(int a, int b)
{
    int tmp = arr[b];
    arr[b]=arr[a];
    arr[a]=tmp;
}

void findlocation(int cur, int last)
{
    int left = cur*2;
    int right = left+1;
    int biggest = cur;

    if(left<=last && arr[left]>arr[cur])
    {
        biggest = left;
    }
    if(right<=last && arr[right]>arr[biggest])
    {
        biggest = right;
    }
    if(biggest==cur) return;
    else
    {
        myswap(cur, biggest);
        findlocation(biggest, last);
    }
}

void heapify(int last)
{
    int cur = last/2;
    while(cur>=1)
    {
        findlocation(cur,last);
        cur--;
    }
}

void addToHeap(int v, int last)
{
    int cur = last+1;
    int parent = cur/2;
    arr[cur]=v;

    if(last==1 && v<0) 
    {
        arr[1]=v;
        return;
    }
    while(1)
    {
        if(arr[parent]>arr[cur])
        {
            return;
        }
        else
        {
            myswap(parent,cur);
            cur=parent;
            parent=cur/2;
            if(parent<1) return;
        }
    }
}

int removeRoot(int last)
{
    int ret = arr[1];
    arr[1] = arr[last];
    findlocation(1,last-1);
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
    int n;
    scanf("%d",&n);

    for(int i=1; i<=n*n; i++)
    {
        int a;
        scanf("%d",&a);
        addToHeap(a,i);
    }
    heapify(n*n);
    for(int i=0; i<n; i++)
    {
        int k = removeRoot(n*n-i);
        if(i==n-1) printf("%d",k);
    }
}