우선 순위 큐 (Priority_Queue)

Priority_Queue(우선순위큐)란?

Queue의 한 종류로 이름 그대로 우선순위에 따라 정렬된 Queue이다.

어떤 원소가 Push()된다면 주어진 우선순위에 맞춰서 Queue가 정렬되고, Pop()는 정렬된 Queue의 앞에서 이루어진다.

자료구조 Heap으로 구현되어있으므로 O(logN)의 실행시간이 걸리게 된다.

 

헤더파일

#include<queue>

 

자료형

priority_queue<자료형, Container, 비교함수> 변수명
// 선언한 자료형 변수들을 비교함수에 따라 정렬하는 메서드

priority_queue<자료형> 변수명
// 선언한 자료형 변수들을 내림차순에 따라 정렬

-empty() : priority_queue() =- null 일때, true or false 반환
- size(): priority_queue() 우선순위의 크기를 반환

 

내림 차순 예제

#include<iostream>
#include<queue>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	priority_queue<int> pq;
	pq.push(5);
	pq.push(11);
	pq.push(1);
	pq.push(6);

	for (int i = 0; i < 4; i++)
	{
		cout << pq.top() << ' ';
		pq.pop();
			
	}


}

 

 

기본 올림차순 예제

 

#include<iostream>
#include<queue>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(5);
	pq.push(11);
	pq.push(1);
	pq.push(6);

	for (int i = 0; i < 4; i++)
	{
		cout << pq.top() << ' ';
		pq.pop();
			
	}


}

 

출력

 

 

추가로 STL을 활용하지 않고 이진트리 구조를 코드로 표현하는 방법은 원소 배열을 대응하여 나타낼 수 있다.

다음과 같이, 배열을 활용하여 힙의 구조를 사용하여 우선순위 큐를 구현할 수 있다.

이때, push(), top(), pop()의 기능을 각 노드의 리프가 부모 노드일때의 상태와, 왼쪽 노드, 우측 노드를 번갈아 비교하며

힙의 이진 트리의 균형적인 구조를 맞춰내며 삽입, 제거 탐색의 기능을 할 수 있다.

 

본 코드는 힙의 최대 힙 혹은 최소 힙의 값을 구하기 때문에 sz번지의 첫번째 인자값을 호출하면 된다.

#include <bits/stdc++.h>
using namespace std;

int heap[100005];
int sz = 0; // heap에 들어있는 원소의 수

void push(int x){
  heap[++sz] = x;
  int idx = sz;
  while(idx != 1){
    int par = idx/2;
    if(heap[par] <= heap[idx]) break;
    swap(heap[par], heap[idx]);
    idx = par;
  }
}

int top(){
  return heap[1];
}

void pop(){
  heap[1] = heap[sz--];
  int idx = 1;
  // 왼쪽 자식의 인덱스(=2*idx)가 size보다 크면 idx는 리프
  while(2*idx <= sz){
    int lc = 2*idx, rc = 2*idx+1; // 왼쪽 자식, 오른쪽 자식
    int min_child = lc; // 두 자식 중 작은 인덱스를 담을 예정
    if(rc <= sz && heap[rc] < heap[lc])
      min_child = rc;
    if(heap[idx] <= heap[min_child]) break;
    swap(heap[idx],heap[min_child]);
    idx = min_child;
  }  
}