19.11.13 (priority queue, deque)

백준 큐 파트를 풀고있다. 큐 자체가 워낙에 뭐 복잡하지 않고 스택이랑 비슷해서 따로 정리글을 올리지 않겠다.

 

boj1966 풀다가 막혀서 찾아보니 priority queue 라는 우선순위 큐 라는 개념을 사용하더라. 이것은 잘 모르니 정리해보겠다.

 

빠르게 이어서 우선순위 큐(priority queue)라는 자료구조를 살펴봅시다. 이니셜은 PQ입니다.

이건 큐가 이름 끝에 붙어 있듯이 push, top, pop 연산밖에는 없는데, 하는 일과 내부 구조는 보통 큐와 완전히 다릅니다.

top, pop에서 추출되는 원소는 제일 먼저 들어왔던 게 아닌, 현재 우선순위 큐 안에서 제일 우선순위가 높은 원소기 때문!!

가장 유명하고 많이 쓰이는 형태는 클수록 우선순위가 높은 형태, 작을수록 우선순위가 높은 형태입니다.

클수록 우선순위가 높다면, pop 연산을 했을 때 제거되는 원소는 들어있던 것들 중 가장 큰 원소입니다.

 

어떤 우선순위 큐의 top에 위치하는 원소가 가장 큰 수라고 할 때,

여기에 1, 4, 3, 7을 순서대로 넣고 pop 연산을 하면 1이 나오는 게 아닙니다.

7이 나옵니다. 그럼 안에는 원소 {1, 3, 4}가 남죠.

여기서 한 번 더 pop을 하면 4가 나오게 되고 {1, 3}이 남습니다.

여기서 6을 push하면 원소는 {1, 3, 6}이 되고, 지금 top은 3에서 6으로 바뀌게 됩니다.

 

우선순위 큐는 보통 힙(heap)이라는 자료구조로 구현됩니다.

보통은 동의어로 많이 쓰이는 편이고, 그래서 top이 최댓값인 우선순위 큐를 최대 힙, 최솟값인 우선순위 큐를 최소 힙이라 부르기도 합니다.

또한 위에서 간파하신 분도 계실지 모르겠지만 어떤 원소들을 다 넣고 pop을 쫙 하면 정렬된 순서로 원소들이 빠져나오게 되는데, 이걸 사용하는 정렬을 힙 소트(heap sort)라고 합니다.

 

힙 역시 많은 언어가 라이브러리로 지원하며, C++의 경우 그래도 이름이 큐여서 <queue> 헤더 파일 안에 존재하고, priority_queue라는 이름의 클래스 템플릿입니다. 기본적으로 최대 힙입니다.

그럼에도 구조를 짚고 넘어가자면, 힙 역시 이진 트리입니다. 그리고 힙은 완전 이진 트리입니다.

구현 난이도는 BST와 크게 차이가 나지는 않는데, BST에 비하면 삭제 연산이 좀 쉽습니다. 더 직관적이고, 삽입과 비슷한 원리이기 때문.

[출처] 우선순위 큐(Priority Queue)|작성자 라이

Ries 마법의 슈퍼마리오 : 네이버 블로그

 

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


// push(element)
pq.push(5);
pq.push(2);
pq.push(8);
pq.push(9);
pq.push(1);
pq.push(14);


// pop()
pq.pop();
pq.pop();

불러오는 중입니다...

 

오름차순이 되어서 최솟값부터 나온다. 만약 greater<int> 가 아니라 less<int>면 최대값부터 나오게 된다.

pq.top()으로 맨 윗값을 확인가능하다.

 

 

 

deque는

https://dream-cy.tistory.com/9

[C++ STL 프로그래밍] 덱 (deque)

이곳을 참조하자.