[C++ STL] std::priority_queue (컨테이너 어댑터)

std::priority_queue

std::priority_queue는 Heap(힙) 자료구조를 기반으로 한 우선순위 큐 자료구조의 컨테이너이다.

 -> 우선순위 큐는 들어간 순서에 상관없이 프로그래머가 정한 우선순위의 근거에 따라 우선순위가 가장 높은 데이터가 먼저 나온다.

 -> 우선 순위큐의 삽입/삭제는 log(N)의 시간복잡도를 가진다. 

  --> 삽입의 경우 완전 이진 트리의 마지막 저장 위치에서 삽입 후 부모와 우선순위를 비교해 올라가는 구조. -> log(N)

  --> 삭제의 경우 루트 노드 삭제 후 완전 이진 트리의 마지막 노드를 루트노드로 옮기고 자식과 우선순위 비교하면서  자기자리를 찾아가는 구조. -> log(N)

 

우선순위 큐는 힙 자료구조(배열)를 채택하였기에 내부 컨테이너는 default로 std::vector로 구현되어 있다.

 -> std::deque도 가능, std::list는 불가능.

디폴트로 vector컨테이너로 구현. 그리고 한가지 디폴트 템플릿 인자가 더 존재한다.(less)

먼저 std::priority_queue 컨테이너를 사용하기 위해서는 <queue> 헤더 파일을 추가해야 한다.

기본적인 생성 방법

// 기본 생성 방식. 
//(default 컨테이너 : vector)
//(default 우선순위 : less(내림차순,최대힙))
std::priority_queue<int> pq;
// 내부 컨테이너 변경.
std::priority_queue<int, std::deque<int>> pq2;
// 우선순위 기준 변경 (사용자 정의 우선순위 기준 넣을 수 있음. 함수 객체)
// greater는 오름차순,최소힙.
std::priority_queue<int, std::vector<int>,std::greater<int>> pq3;
// 복사 생성자 지원한다.
std::priority_queue<int> pq4(pq);

또는

std::vector<int> v{ 10,15,30,5,22,17 };
std::priority_queue<int> pq(v.begin(),v.end());

위와같이 미리 데이터를 넣어줄 수 있다. (vector가 아닌 일반 배열의 범위도 가능)

 

우선순위 기준을 사용자가 정의한 우선순위로 넣을 수 있다.

1.  priority_queue의 템플릿 마지막 인자로 함수객체( ()연산자를 오버로딩)를 넣는 방법. 

2. 클래스,구조체에서 < 연산자를 오버로딩하여 템플릿 인자 기본으로 넘겨주는 방법.

 -> 멤버함수의 설명에서 이어서 설명

 

이제 멤버함수를 보자.

 

1. push,pop 함수

//Default 최대힙(내림차순).
std::priority_queue<int> pq;
    
pq.push(9);
pq.push(5);
pq.push(1);
pq.push(4);
pq.push(3);
pq.push(7);
     
pq.pop(); // 값이 가장 높은 9가 먼저 나온다.

push함수. priority_queue컨테이너에 데이터를 삽입하는 함수. 삽입 시 생성할 떄 정해진 우선순위의 기준에 따라 본인의 자리를 찾는 과정이 존재한다.

위 코드에서 9,5,1,4,3까지 데이터가 들어갔다고 보자. 마지막으로 7이 들어갈려는 상황.

출처 -&amp;amp;amp;amp;amp;amp;amp;amp;nbsp;https://www.programiz.com/dsa/priority-queue

우선 우선순위 큐에서 데이터를 삽입할 때 완전 이진 트리에서 다음 저장할 순서에 먼저 데이터를 넣게 된다.

 -> 완전 이진 트리에서 2의 오른쪽이 다음에 저장할 장소.

그러고 난 후 우선순위 기준에 따라 부모와 우선순위를 비교한다. 위 코드는 최대힙(내림차순)이 기준이므로 부모인 5는

새로 들어온 7보다 값이 작으므로 서로 위치를 바꾼다.

출처 -&amp;amp;amp;amp;amp;amp;amp;amp;nbsp;https://www.programiz.com/dsa/priority-queue

서로 자리를 바꾸고 난 후 7은 다시 부모와 우선순위를 비교한다. 부모인 9는 자기보다 우선순위가 높으므로 바꾸지 않는다.

 -> 자기자리를 찾음.

삽입의 과정은 이렇다.

 

이제 pop의 경우에는 우선순위가 가장 높은 요소가 빠져나온다. 즉 9가 빠져나오게 된다는 이야기.

출처 -&amp;amp;amp;amp;amp;amp;amp;amp;nbsp;https://www.programiz.com/dsa/priority-queue

9가 빠져 나오면 완전 이진 트리의 가장 마지막 노드를 루트노드로 올리고, 자식과 우선순위를 비교하면서 자기자리를 찾는다.

 -> 만약 자식과 우선순위를 비교할 때 둘 다 우선순위가 자신보다 높다면 자식들 중 더 높은 우선순위와 교체.

출처 -&amp;amp;amp;amp;amp;amp;amp;amp;nbsp;https://www.programiz.com/dsa/priority-queue

5는 자기자식들과 비교한 후 오른쪽 자식인 7이 우선순위가 더 높아 교체한 후 2와 비교하고 자기자신이 우선순위가 높아 2번 자리에 안착한다.

 

이게 priority_queue의 push,pop과정.

 

2. top 함수

//Default 최대힙(내림차순).
std::priority_queue<int> pq;
    
pq.push(9);
pq.push(5);
pq.push(1);
pq.push(4);
pq.push(3);
pq.push(7);
    
const int size = pq.size();
for (int pop = 0; pop < size; ++pop)
{
    std::cout << pq.top() << " ";
    pq.pop();
}

실행 결과

우선순위가 높은(내림차순,최대힙)순서대로 나온것을 알 수 있다.

이렇게 top함수는 우선순위 큐가 이루는 완전 이진 트리에서 루트 노드를 반환한다.

 

 

3. 사용자 정의 우선순위

 

사용자 정의 우선순위를 넘기는 방법은 밑과 같이 있다고 했다.

1.  priority_queue의 템플릿 마지막 인자로 함수객체( ()연산자를 오버로딩)를 넣는 방법. 

2. 클래스,구조체에서 < 연산자를 오버로딩하여 템플릿 인자 기본으로 넘겨주는 방법.

 

먼저 1번부터 보자

struct Student
{
    Student(int id, int kor, int math, int eng) : m_id(id), m_kor(kor), m_math(math), m_eng(eng) 
    {
        m_avg = (m_id + m_math + m_eng) / 3;
    }
    int m_id;
    int m_kor;
    int m_math;
    int m_eng;
    int m_avg;
};
 
struct Comp
{
    bool operator()(const Student& lhs, const Student& rhs)
    {
        return lhs.m_avg < rhs.m_avg; // 내림차순
    }
};
 
int main()
{    
    ::srand(::time(nullptr)); // random한 성적을 주기 위함.
    // 함수객체(Comp)를 넘겨 우선순위 기준 변경.
    std::priority_queue<Student,std::vector<Student>,Comp> pq;
}

먼저 학생이라는 구조체를 하나 정의하였고, 1번에서 말한 함수 객체를 priority_queue의 마지막 템플릿 인자로 넘겨 우선순위 기준을 변경하였다. (성적의 평균이 큰 순서대로 내림차순)

 

이제 실제 데이터를 넘기고 확인해보면

int main()
{    
    ::srand(::time(nullptr));
   // 함수객체(Comp)를 넘겨 우선순위 기준 변경.
    std::priority_queue<Student,std::vector<Student>,Comp> pq;
 
    for (int push = 0; push < 5; ++push)
    {
        Student s(push + 1, rand() % 101, rand() % 101, rand() % 101);
        pq.push(s);
        std::cout << push + 1 << "번째 학생의 평균 : " << s.m_avg << std::endl;
    }
 
    std::cout << std::endl;
 
    const int size = pq.size();
    for (int pop = 0; pop < size; ++pop)
    {
        const Student& s = pq.top();
        std::cout << s.m_id << "학생 평균 : " << s.m_avg << std::endl;
        pq.pop();
    }
    
    return 0;
}

결과.

학생들의 평균 성적을 높은 순서대로 (내림차순) 빠져나오는것을 알 수 있다.

이렇게 함수객체를 이용한 방법이 있다.

 

이제 2번을 보자.

함수객체를 이용하여 사용자 정의 자료형의 우선순위 기준을 넘겨줄 수 있지만, 구조체나 클래스에서 < 연산자를 오버로딩하여 템플릿 인자로 넘길필요 없이 내부적으로 처리하게끔 동작할 수 있다.

struct Student
{
    Student(int id, int kor, int math, int eng) : m_id(id), m_kor(kor), m_math(math), m_eng(eng) 
    {
        m_avg = (m_id + m_math + m_eng) / 3;
    }
    // < 연산자 오버로딩. (const 멤버함수여야한다)
    bool operator<(const Student& other) const
    {
        return this->m_avg < other.m_avg; // 내림차순
    }
    int m_id;
    int m_kor;
    int m_math;
    int m_eng;
    int m_avg;
};

Student 구조체를 위와 같이 < 연산자 오버로딩을 추가해주고. (const 멤버함수이여야 함.)

메인 함수에서 priority_queue의 템플릿 마지막 인자에 함수 객체를 넘길필요 없이

std::priority_queue<Student> pq;

위와 같이 생성해주고, 나머지 코드를 그대로 고치지 않고 실행해보면

똑같이 성적의 평균을 기준으로 최대힙,내림차순으로 동작하는것을 알 수 있다.

 

 

정리.

priority_queue가 컨테이너 어댑터의 마지막.

앞에서 몇번 말했지만 다른 컨테이너(시퀀스,연관등)는 데이터를 어떻게 저장할지(선형적,비선형적)에 따른 각 장단점이 존재했지만, 컨테이너 어댑터는 인터페이스를 제공하는게 주 목적.

 -> 그렇기에 반복자, 범위기반 for문의 사용이 불가능.