우선 순위 큐(Priority Queue) 사용하기

프로그래밍을 하다보면 사용하게되는 자료구조 중에 하나인 Queue는 데이터를 넣은 순서대로 나오는 것이 기본이다.

ex) 입력 : 6, 4, 5, 3, 2, 1
      출력 : 6, 4, 5, 3, 2, 1

하지만 필요에 따라서는 정렬되어 나왔으면 하는 경우가 있다. 예를들자면(적절한 비유인지는 모르겠지만) 은행에서 우수고객을 선발할 때 계좌 개설일 순서로 하지 않는다라든지, 응급실에서는 위급한 환자를 먼저 살핀다든지 하는 경우를 들 수 있겠다. 앞의 예를 Priority Queue에서 보면 아래와 같다.

ex) 입력 : 6, 4, 5, 3, 2, 1
      출력 : 6, 5, 4, 3, 2, 1

대충 내용은 이런 것이고 이제 어떻게 생겼는지 살펴보자.

template <
   class Type,
   class Container=vector<Type>,
      class Compare=less<typename Container::value_type>
>
class priority_queue

보면 아시겠지만 클래스 템플릿이다. 저 파라메터들은 다 뭔가? 다음을 보자.

Type 
        우선 순위 큐에 담을 데이터의 타입           
Container 
        우선 순위 큐를 구현하는데에 기본이되는 컨테이너         
Compare 
        우선 순위 큐의 정렬 기준이 되는 비교 함수 또는 클래스

이제 사용해보자.
                        ...
#include <queue>
                        ...
bool Search(...)
{
                        ...
        priority_queue<int, vector<int>, greater<int>> OpenIndexList;
                        ...
        int index;
                        ...
        OpenIndexList.push(index);
                        ...
        while(!OpenIndexList.empty())
        {
              int index = OpenIndexList.top();
                        ...
              OpenIndexList.pop();
        }
                        ...
}

...은 딴짓을 한다는 이야기다. 그러나 Priority Queue의 사용에 대한 부분은 모두 나와 있으므로 참고하시면 되겠다.

한가지 더, 임의의 데이터 타입을 사용하는 경우는

        // TEMPLATE STRUCT greater
template<class _Ty>
    struct greater
        : public binary_function<_Ty, _Ty, bool>
    {    // functor for operator>
        bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {    // apply operator> to operands
            return (_Left > _Right);
        }
    };

        // TEMPLATE STRUCT less
template<class _Ty>
    struct less
        : public binary_function<_Ty, _Ty, bool>
    {    // functor for operator<
        bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {    // apply operator< to operands
            return (_Left < _Right);
        }
    };

이 템플릿을 사용해서 비교 연산을 사용할 수 있도록

//Overload the < operator.
bool operator< (const Student& struct1, const Student &struct2)
{
    return struct1.nAge > struct2.nAge;
}

//Overload the > operator.
bool operator> (const Student& struct1, const Student &struct2)
{
    return struct1.nAge < struct2.nAge;
}

이렇게 >< 연산자까지 overload 해주면 금상첨화다.