priority queue(우선순위 큐)(C++)(알고리즘)

위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.

알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.

강의링크

우선순위 큐란 무엇인가?

우선순위 큐(priority queue)는 각 요소에 어떠한 우선순위가 추가로 부여되어있는 컨테이너를 말합니다.

우선순위 큐에서 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 제공됩니다. 일부 구현에서 두 요소의 우선 순위가 같으면 대기열에 포함된 순서에 따라 제공됩니다. 다른 구현에서 동일한 우선 순위를 가진 요소의 순서는 정의되지 않은 상태로 유지됩니다.

• 힙은 완전이진트리로 최소힙 또는 최대힙이 있으며 삽입, 삭제, 탐색, 수정에 대해 O(logN)의 시간복잡도를 갖습니다. 최대 힙은 로트 노드에 최대값이 있고, 최소 힙은 루트노드에 최소값이 있는 힙입니다.

 

int형 우선순위큐

단순하게 int형 우선순위큐는 다음 코드 처럼 greater 를 써서 오름차순, less를 써서 내림차순으로 바꿀 수 있습니다. 기본값은 내림차순이라 단순하게 priority_queue<타입>을 쓰면 해당 타입에 대한 내림차순으로 설정됩니다.

#include <bits/stdc++.h> 
using namespace std; 
priority_queue<int, vector<int>, greater<int> > pq; //오름차순
priority_queue<int> pq2; // 내림차순 
priority_queue<int, vector<int>, less<int> > pq3; // 내림차순 
int main(){ 	
    for(int i = 5; i >= 1; i--){ 		
        pq.push(i); pq2.push(i); pq3.push(i); 	
    } 	
    while(pq.size())
    { 		
        cout << pq.top() << " : " << pq2.top() << " : " << pq3.top() << '\n'; 		
        pq.pop(); pq2.pop(); pq3.pop(); 	
    } 	
    return (0); 
} 
/* 1 : 5 : 5 2 : 4 : 4 3 : 3 : 3 4 : 2 : 2 5 : 1 : 1 */

메서드는 stack과 같습니다. size(), top(), pop(), push()가 있습니다.

 

Uploaded by

N2T