[C++] STL을 이용한 우선순위 큐(priority queue)

저번 포스팅에서는 우선순위 큐와 힙에 대한 내용을 정리해 보았다.

그런데 우선순위 큐를 사용하기 위해서는 코드를 일일이 구현해야 하는 걸까?

그렇지 않다. C++에서는 STL(표준 C++ 라이브러리 Standard Template Library) 을 통해 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하고 있다. 오늘은 이 STL을 이용한 우선순위 큐에 대해 알아본다.

 

이에 앞서 STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다는 사실을 짚고 넘어가면 좋을 것 같다.

 

priority queue는 기본적으로 아래와 같은 문법으로 선언한다.

#include <queue>
priority_queue<int, vector<int>, less<int>> queue;

첫 번째 인자는 타입을 지정한다.

두 번째 인자는 컨테이너를 지정하는데, 이는 아래에서 다시 설명한다.

세 번째 인자는 max heap을 사용할 것인지 min heap을 사용할 것인지 지정할 수 있다. 디폴트는 max heap이며 less<자료형> 비교 함수를 사용한다. min heap을 사용하려면 greater<자료형>을 넣으면 된다.

 

STL에서 컨테이너란 같은 타입의 여러 객체를 저장하는 일종의 집합인데, 쉽게 말해 자료구조라고 생각하면 될 듯 하다.

자료구조가 다 똑같을 것 같지만 STL에서는 자료를 저장하는 방식과 관리하는 방식에 따라 컨테이너를 달리 분류한다.

 

priority queue는 컨테이너 어댑터에 해당한다.

컨테이너 어댑터에 대해서 부연하자면, 먼저 어댑터(adapter) 패턴의 개념에 대해 이해하면 좋다.

어댑터 패턴이란 클래스의 인터페이스를 사용자가 기대하는 다른 인터페이스로 변환하는 패턴을 의미한다. 호환성이 없는 인터페이스 때문에 함께 동작할 수 없는 클래스들이 함께 작동하도록 해준다. 즉 서로 다른 인터페이스 사이에서 중재자 역할을 해준다고 보면 된다.

 

그렇다면 컨테이너 어댑터란 무엇일까?

컨테이너 어댑터는 시퀀스 컨테이너(vector, list, deque)의 인터페이스를 제한하거나 변형해 특정 동작만 할 수 있게 만든 컨테이너다. 기존의 컨테이너를 사용자의 필요에 맞춰 다른 형태의 자료구조로 변환했다는 것이다.

 

이제 priority queue 선언 시 두 번째 인자로 컨테이너를 지정하는 이유를 알았다.

여기서 사용할 컨테이너는 임의 접근 반복자와 우선 순위 큐에 필요한 연산들을 모두 제공해야 한다.

priority queue에서는 vector와 deque가 조건을 충족하므로 컨테이너로 사용 가능하다.

 

 

위 내용을 이해했다면 우선순위 큐를 사용하는 것은 어렵지 않다. 함수만 검색해서 쓰면 된다.

따라서 관련 내용은 이 글에 적지 않고, 마지막으로 우선순위 큐가 내부적으로 어떻게 동작하는지 부연하겠다.

 

알다시피 STL의 priority queue에서는 힙 구조를 사용하는데, 이는 배열 요소가 push될 때마다 자동으로 정렬된다는(추가된 배열 요소가 자리를 찾아간다는) 뜻이다.

그렇다면 배열 요소가 pop될 때는 어떨까? 사실은 이 때 힙 정렬 작업이 이루어진다. 힙은 애초에 완전정렬 상태가 아니기에 루트 노드가 제거될 때 다시 정렬이 되어야 한다. 디버깅을 통해 우선순위 큐가 작동하는 모습을 살펴보면 이해가 될 것이다.

 

 

 

 

 

참고

http://tcpschool.com/cpp/cpp_container_intro

https://fromleaf.tistory.com/39