[C++] 우선순위 큐 (priority_queue) STL 사용법, 구현, 정렬

우선순위 큐

우선순위가 가장 높은 자료가 먼저 꺼내진다는 특징이 있다.

이런 큐를 구현하기 위해서는, 모든 원소를 순회하며 우선순위가 가장 높은 원소를 찾는 방법이 있다. 그러나 여기서는 힙이라는 단순한 구조의 이진 트리를 사용해서 새 원소를 추가하고 꺼내는 연산을 O(logN)에 수행한다.

힙

• 힙의 대소 관계 규칙
  • 부모 노드가 가진 원소는 자식 노드가 가진 원소보다 크거나 같다.
  • 왼쪽/오른쪽 자식에 대한 크기 제약은 없다.
• 힙의 모양 규칙
  • 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있어야 한다.
  • 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있다.

 

STL priority_queue 사용법

#include <queue>

priority_queue<자료형, Container, 비교함수> 변수명; 
ex) priority_queue<int, vector<int>, cmp> pq;

priority_queue<자료형> 변수명
ex) priority_queue<char> pq;

헤더를 추가해서 선언한다. 

이 때, 비교자 없이 두 번째 방법으로 선언하게 되면 기본적으로 내림차순 (최대힙)의 형태로 내부 요소를 정렬한다. 

 

추가 및 삭제 

push(element) // 원소를 삽입한다. 내부적으로 정렬된다. 
pop() // 맨 앞에 있는 원소를 삭제한다.

 

서칭

top() // 맨 앞에 있는 원소를 반환

 

기타

empty() // Priority_queue가 비어있다면 true, 원소가 하나라도 있다면 false를 반환
size() // priority_queue의 크기를 반환

 

배열을 이용한 Heap의 구현

배열을 이용한 힙의 구현

트리 상에서 아래와 같이 일차원 배열을 표현하게 되면, A[i] 노드에 대한 정보는 다음과 같이 정리할 수 있다.

1. 왼쪽 자손은 A[2 x i + 1] 에 대응된다.
2. 오른쪽 자손은 A[2 x i + 2] 에 대응된다.
3. 부모 노드는 A[(i - 1)/2]에 대응된다.

이는 vector<int>heap으로 원소를 저장할 수 있다.

 

새 원소의 삽입

힙에서는 대소 관계 규칙보다 모양 규칙을 우선하기 때문에, 새 노드는 항상 heap[]의 가장 마지막에 추가된다.

그 다음, (1) 이 원소를 부모 노드와 비교해서, 부모 노드가 더 작다면 위치를 바꾼다. (2) 새롭게 들어온 원소가 더 크거나 같으면 루트에 도달할 때까지 반복한다.

void push_heap(vector<int>& heap, int newValue) {
    heap.push_back(newValue);

    int idx = heap.size() - 1;
    // 루트에 도달하거나, 새로 들어온 노드가 부모 노드보다 크면
    while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
        swap(heap[idx], heap[(idx - 1) / 2]);
        idx = (idx - 1) / 2; 
    }
}

 

최대 원소 꺼내기

 

힙의 최대 원소는 힙의 첫 원소에 있다. 이를 꺼내면 루트 노드는 빈 노드가 되고, 우리는 가장 마지막 노드를 가져와 여기에 넣어준다. (힙의 모양 규칙)

그 다음, 자식 노드와 비교해서 더 큰 원소를 선택해 바꿔준다. 이를 트리의 바닥까지 도달하거나, 두 자손이 자기 자신보다 작은 노드들만을 자식으로 가지고 있을 때까지 반복한다. (힙의 대소 관계 규칙)

// heap[0]을 제거하고 힙의 모양 규칙과 대소 관계 규칙을 만족시키는 과정
void pop_head(vector<int>& heap) {
    heap[0] = heap.back();
    heap.pop_back();

    int here = 0;
    while (true) {
        int left = here * 2 + 1, right = here * 2 + 2; 
        // 리프에 도달한 경우 종료
        if (left >= heap.size()) break;

        // next : heap[here]가 내려갈 위치
        int next = here;
        // 왼쪽이 더 크면 왼쪽으로 이동
        if (heap[next] < heap[left])
            next = left;
        // 오른쪽이 더 크면 오른쪽으로 이동
        if (right < heap.size() && heap[next] < heap[right])
            next = right;
        // heap[next]가 가장 큰 경우 next는 이동하지 않았다.
        if (next == here) break;
        swap(heap[here], heap[next]);
        here = next; 
    }
}

 

priority_queue 정렬하기 

1. greater, less를 이용한 정렬

priority_queue<int, vector<int>, greater<int>()> maxHeap; // 내림차순 정렬
priority_queue<int, vector<int>, less<int>()> minHeap; // 오름차순 정렬

 

2. 비교자 함수를 이용한 정렬

struct Person {
    string name;
    int age;

    // 비교자 함수
    struct Compare {
        bool operator()(const Person& p1, const Person& p2) {
            return p1.age < p2.age;  // 나이를 기준으로 내림차순 정렬
        }
    };
};

priority_queue<Person, vector<Person>, Person::compare> pq;

구조체 Person을 선언하고 내부적으로 Compare 함수를 선언해 나이를 기준으로 내림차순 정렬하는 예제이다.

 

비교자 함수를 이용하여 정렬하는 또 다른 예제이다. 

두 수의 절댓값이 큰 것을 우선으로 정렬하되, 절댓값이 같다면 양수인 것을 우선으로 두는 코드이다.

strcut cmp{
	bool operator()(int n1, int n2){
    	if(abs(n1) == abs(n2))
        	return n1 > n2; 
        else
        	return abs(n1) > abs(n2); 
	}
}

priority_queue<int, vector<int>, cmp> pq;