[C++ STL 만들기] priority_queue 구현

STL priority_queue

    이번 글에는 STL의 <queue> 헤더파일에 존재하는 내부 함수 우선순위 큐를 직접 구현해보았다. priority_queue를 C++ STL 홈페이지(https://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue)에서 찾아볼 경우 다음과 같이 나온다.

초록색 글씨를 보면 선언할 때 변수의 type(class도 가능)을 받고 두 번째 인자로 우선순위 큐를 구성하는 컨테이너, 즉 배열을 선언할 수 있다. 기본값으론 vector를 사용한다. 마지막 인자로 힙을 구성하는 비교 함수 연산자가 있는 class를 포함한다. 기본값인 less는 최대힙을 만들 때 사용한다. 최소힙으로 사용하고 싶을 경우 greater를 사용한다. 다음과 같이 최대힙, 최소힙을 선언할 수 있다.

#include <queue>

priority_queue<int, vector<int>, less<int>> pq; //최대힙
priority_queue<int, vector<int>, greater<int>> pq; //최소힙

 

우선순위 큐 동작 방식

 우선순위 큐는 힙을 이용한다. FIRST IN FIRST OUT인 queue와 다르게 우선순위가 높은 인자가 우선적으로 나온다. 힙의 push와 pop은 다음과 같이 동작한다. 예시는 5, 6, 3, 7, 10, 4가 순서대로 push될 경우 최대힙이 만들어지는 과정이다.

힙은 언제나 완전 이진트리이다. 동작방식은 다음과 같다.

 

삽입

• 삽입하려는 값을 트리의 맨 마지막에 넣는다.
• 부모노드와 비교하며 삽입하려는 값이 더 큰 경우 부모노드와 값을 바꾼다.
• 삽입하려는 값보다 큰 값이 나오지 않을 때까지 반복한다.
• 만약 root노드보다 삽입하려는 값이 큰 경우 root노드에 저장한다.

삭제

• 트리의 맨 아래의 맨 오른쪽에 있는 원소인 pivot을 root노드로 위치시킨다.
• 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 비교한다.
• 자식 노드가 더 큰 경우 자식노드와 값을 바꾼다.
• pivot 값보다 작은 값을 만날 때까지 반복한다.
• 만약 leaf노드까지 도달한 경우 pivot 값을 leaf노드에 저장한다.

우선순위 큐는 위의 과정으로 동작한다. 여기서 비교하는 함수는 선언의 마지막 인자에 있는 class를 이용하여 비교연산을 한다. 

 

priority_queue 코드 설명

class의 구조와 멤버 변수는 다음과 같다.

template <class T, class CONT = std::vector<T>, class CMP = less<typename CONT::value_type>>
class mypriority_queue {
private:
    CONT container;
    int num;
    CMP compare;
}

 

    맨 첫 번째 줄을 보면 글 맨 위에 있는 사진에서 확인할 수 있듯이 template를 동일하게 선언하였다. 타입, 컨테이터, 비교클래스.

    멤버변수는 template로 선언한 container가 컨테이너, num은  원소의 수를 나타내고 compare는 비교를 실행할 인스턴스이다. 비교 클래스를 받기 때문에 클래스 안에 있는 비교함수나 연산자를 이용하기 위해선 그 class를 타입으로 가지는 인스턴스가 존재해야하기 때문에 선언하였다. 예를 들어 CMP안에 ()연산자가 정의된 경우 compare(a, b)와 같이 사용하여 비교연산을 수행할 수 있다.

 

사이트에 나와있는 멤버 함수는 다음과 같다.

이 중에 구현한 함수는 생성자를 포함해 empty, size, top, push, pop을 구현하였다. 다른 함수들은 많이 사용되지 않기 때문에 생략하였다.

 

소스 코드

아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/mypriority_queue.cpp

GitHub - Seo-sang/Cpp-_Standard_Template_Library: make C++ STL myself