우선순위 큐 (priority_queue)

1. 우선순위 큐 (priority_queue)

데이터를 큐에 넣을 때 자동으로 내림차순(혹은 오름차순)으로 정렬되어 들어간다.

우선순위 큐는 힙 트리로 구성되어있다.

 

2. 힙 트리 (Heap Tree)

이진 트리로 구성되어 있음.

부모 노드의 데이가 자식 노드보다 항상 크거나(최대 힙), 항상 작은(최소 힙) 트리.

-> 정렬되어 있는 이진 트리

 

3. 힙 트리의 조건

1) 힙 트리는 반드시 최대 힙 또는 최소 힙이어야 한다.

- 자식 트리 간의 서열은 없다.

 

2) 노드 개수를 알면 트리 구조는 확정할 수 있다.

- 완전 이진 트리 ; 마지막 레벨을 제외한 모든 레벨이 노드가 꽉 차있어야 한다(균형을 이룸).

- 마지막 레벨에 노드가 있다면, 트리의 왼쪽부터 순서대로 채운다.

 

4. 힙 트리의 규칙성

1) i 번째 노드의 왼쪽 자식의 인덱스는 (2 * i) + 1

2) i 번째 노드의 오른쪽 자식의 인덱스는 (2 * i) + 2

3) i 번째 노드의 왼쪽 자식의 인덱스는 (i - 1) / 2

 

5. 새로운 값이 추가되는 상황

1) 트리의 맨 좌측에 값을 추가

 

2) 최대 힙(또는 최소 힙) 조건에 따라 정렬

 

6. 최대값 추출하기

(1) root 트리를 제거(pop)한다.

(2) 최하위 노드(leaf)노드를 root로 옮긴다.

(3) 데이터를 재정렬한다.

 

 

7. 코드

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

template<typename T>
class PriorityQueue
{
public:

    void push(const T& data)
    {
        _heap.push_back(data);

        // 정렬 시작
        int now = static_cast<int>(_heap.size()) - 1;

        // 루트 노드까지 도달하기
        while (now > 0)
        {
            int next = (now - 1) / 2;

            if (_heap[now] < _heap[next])
                break;

            // 데이터 교체하기
            std::swap(_heap[now], _heap[next]);

            // 부모로 올라갔으면 인덱스를 대체해주기
            now = next;
        }
    }

    void pop()
    {
        // 데이터(->루트) 교체
        _heap[0] = _heap.back();
        _heap.pop_back();
        
        int now = 0;

        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;

            // 리프에 도달시 종료
            if (left >= (int)_heap.size())
                break;

            int next = now;

            // 왼쪽과 비교
            if (_heap[next] < _heap[left])
                next = left;

            // 왼쪽과 자신의 승자를 오른쪽과 비교하기
            if (right < _heap.size() && _heap[next] < _heap[right])
                next = right;

            // 왼쪽과 오른쪽 둘 다 현재 값보다 작으면 종료하기
            if (next == now)
                break;

            std::swap(_heap[next], _heap[now]);
        }
    }

    T& top()
    {
        return _heap[0];
    }

    bool empty()
    {
        return _heap.empty();
    }

private:
    vector<T> _heap;
};