priority queue

우선순위 큐!

이게 무슨 말이냐면요

우선순위를 넣을 수 있는 큐에요!

끄읕

 

아 진짴ㅋㅋㅋㅋㅋ 갑자기 피곤해서 글 쓰는게 귀찮아졌어요...ㅋㅋㅋ

 

제대로 설명을 드리자면 큐에 요소를 하나씩 담는데 우선순위를 부여할 수 있는 컨테이너를 말해요.

 

이렇게 큐에 요소들이 담겨있는데 9가 우선순위로 부여가 되어있어 우선순위가 낮은 요소보다 먼저 제공이 된다는 것이죠.

 

만약에 두 요소의 우선순위가 같으면 대기열에 포함된 순서에 따라 제공이 됩니다.

또 만약에 동일한 우선순위를 가지고 있는데 요소의  순서는 어떻게 정의가 되냐면

정의되지 않습니다.

그대로 유지에요.

 

우선순위 큐는 FIFO형태가 아닌 우선순위가 높은 요소가 먼저 나가는거에요.

우선순위 큐는 Heap을 통해 구현이 되는데요.

 

힙(Heap)?

힙은 우선순위 큐를 위해 고안된 완전 이진트리 형태의 자료구조에요.

 

최대힙과 최소힙이있는데

최대힙

최대 힙(MaxHeap)은 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진트리에요.

 

최소힙

최소 힙(Min Heap)은 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진트리입니다.

 

여기서 힙의 특징은 완전 이진트리 형태로 이루어져 있는데 최대값과 최솟값을 찾아내는 연산이 빠른 구조중 하나입니다.

근데 이진트리(BST)와 달리 중복도니 값이 허용이 되는 것을 볼수가 있어요.

 

일단 함수를 봐보죠.

 

push(value)

우선순위 큐에 value요소를 추가

 

top()

우선순위 큐에 맨 위 요소를 참조합니다.

pop()

우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환합니다.

size()

우선순위 큐의 사이즈를 반환합니다.

 

 

힙은 일반적으로 배열을 이용해서 구현하는데 완전 이진트리이기 때문에 중간에 비어있는 요소가 없습니다.

배열로 구현하기 때문에 자식노드를 찾아가는 연산을 구현하기도 편합니다.

 

왼쪽 자식노드의 Index = 부모노드index * 2

오른쪽 자식노드의 Index = (부모노드Index * 2) + 1

 

부모노드의 Index = 자식노드 Index / 2

 

그렇다면 여기서 삽입과 삭제의 시간 복잡도를 안 볼수가 없다.

 

삽입

완전 이진트리이므로 마지막 노드에 이어서 새로운 노드를 추가해주어야 합니다.

추가된 새로운 노드를 부모의 노드와 비교해서 교환합니다.

더이상 부모노드와 교환할 필요가 없을 때까지 이 방식을 반복합니다.

 

그렇기에 최악의 경우에는 새로 추가된 노드가 루트노드까지 비교하여 올라가야 하니 시간복잡도가 O(log2n)입니다.

 

삭제

1. 루트노드가 가장 우선순위가 높아서 루트 노드를 삭제해야 합니다.

2. 루트 노드가 삭제된 빈자리에 완전 이진트리의 마지막 노드를 가져옵니다.

3. 루트자리에서 위치한 새로운 노드를 자식 노드와 비교해서 교환합니다.

4. 이 때 최대 힙일 경우 자식노드 중 더 큰 값과 교환하며 최소 힙인 경우 더 작은값을 교환합니다.

5. 더 이상 자식 노드와 교환할 필요가 없을 때까지 이 방식을 반복합니다.

 

삭제 연산 또한 최악의 경우 루트노드부터 가장 아래까지 내려가야 해서 시간복잡도가 O(log2n)입니다.

 

코드로 사용해봅시다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    // MaxHeap이다
    // less로 비교하니 내림차순이기 때문이다.
    priority_queue<int, vector<int>, less<int>> pq_less;
    
    pq_less.push(3);
    pq_less.push(1);
    pq_less.push(5);
    pq_less.push(2);
    
    pq_less.pop();
    pq_less.pop();
    
    while (!pq_less.empty())
    {
        cout << pq_less.top() << " ";
        pq_less.pop();
    }
    
    cout << '\n';
}

 

결과값은

 

 

이렇습니다.

뭐 근데 이것을 디버깅해서 보면은

그래프는 이렇게 되더라구요.

 

이것을 트리로 보자면

오른쪽과 같더군요.

근데 분명 내림차순인데 왜 5, 2, 3, 1로 들어가게 되는지..?

 

우선순위 때문입니다.

 

우선순위 큐는 먼저 들어온 순서가 우선순위가 높아지는게 있더라구요.

 

먼저 3이 들어왔습니다.

 

pq_less.push(3);

 

그럼 3의 우선순위는 지금 1위입니다.

그다음 1이 들어왔어요.

pq_less.push(1);

 

 

1을 삽입할 때 부모랑 비교합니다 MaxHeap이니 부모보다 커야 교환을 할 수가 있죠

하지만 1은 부모보다 작으니 그자리에 그대로 있게됩니다.

 

 

pq_less.push(5);

그 다음은 5가 들어왔습니다.

 

새로운 노드를 배치하고 부모보다 큰지(MaxHeap) 검사합니다.

5가 더 크니 자리를 바꾸어야 겠죠?

 

잠시나마 최상위에 있던 3이 웁니다.

지금까지의 과정을 디버깅으로 검사해보죠.

3이들어왔네요.

1이 들어왔을 때 3, 1이 맞네요.

 

음 이것도 순서가 맞네요 5, 1, 3 그래프로 보면 

 

 

이게 맞으니까요.

 

그러면 이제 여기서 2를 삽입합니다.

 

2가 새로운 노드로 정착했어요.

그러면 부모가 나보다 작은지 검사하게 됩니다.

2가 1보다 크니 자리를 빼앗기게 되겠죠.

 

그렇다면 2는 다시 부모의 검사를 하게 되는데 5가 당연히 2보다 크니 자리는 교환하지 않고 끝나게 됩니다.

그러면 배열에 들어간 것으로는

 

이런식의 순서로 들어가게 되겠네요?

 

 

정확하네요.

 

그러면 여기서 이제 삭제를 눈으로 확인해보죠.

 

우선순위가 제일 높은 거부터 삭제가 됩니다.

그리고 맨 마지막 노드를 잠시 최상위 자리로 올리죠.

그러면 여기서 이제 자식노드랑 검사를 하게 됩니다. MaxHeap이니 나보다 큰지 검사합니다.

제일 우선순위가 높은(MaxHeap) 숫자로 자리를 바꾸게 됩니다.

 

이제 여기서 더 이상 자식노드를 검사할 게 없는 1은 여기서 끝나게 되죠.

 

이해가 가실지 모르겠지만 최대한 그림으로 설명해봤어요.

 

저도 처음에는 이해가 잘 가지 않았지만 하다보면 이해가 가더라구요!

 

아무튼 오늘은 여기서 끄으읕