C, C++/자료구조 / / 2024. 6. 10.

[C++] 우선 순위 큐 ( Priority Queue ) 사용법

 

우선순위 큐 ( Priority Queue )

우선순위 큐는 저장하고 있는 원소들을 원소의 우선순위 순으로 정렬한 자료 구조입니다.

 

일반 큐(queue)는 FIFO( first in, first out ) 방식으로, 먼저 입력된 순으로 출력되지만,

우선순위 큐는 원소가 가진 우선순위 순으로, 출력되는 순서가 결정되는 queue입니다.

 

우선순위 큐의 원소 배치를 이미지로 나타낸다면 다음과 같습니다.

이 자료구조는 원소를 입력받을 때마다, 가장 높은 우선순위를 가진 원소가 트리의 최상위에 위치하도록 정렬을 수행합니다.

그렇기 때문에, 최대 값이나 최소 값을 구하는데 매우 빠른 수행시간을 보여줍니다.

 

우선순위 큐

 

이러한 우선순위 큐는 허프만 코드를 이용한 데이터 압축, 스택 구현, 네트워크의 트래픽 제어, 운영체제 작업스케줄링 등에 사용됩니다.

 

우선순위 큐를 사용하려면 우선 헤더 파일을 포함해야 합니다.

#include <queue>

 

우선순위 큐의 선언은 다음과 같습니다.

std::priority_queue< T, Class<T> = vector<T>, Compare = less<T> > queue_name;

여기서 T는 원소의 데이터 타입을 말합니다.

 

Class는 우선순위 큐를 구성하는데 필요한 실제 원소들을 담고 있는 컨테이너입니다.

외부로 노출되는 것은 우선순위의 큐이지만, 실제 데이터의 입출력을 수행하는 클래스입니다.

STL에서는 queue와 vector 컨테이너를 권장하지만, 사용자 컨테이너도 필요한 함수와 iterator를 지원한다면 사용할 수 있습니다.

기본값으로 vector 클래스를 사용합니다.

 

나머지 인자인 Compare는 우선순위 큐의 원소를 정렬하는 방식을 결정하는 함수 객체입니다.

이것은 "비교 함수 객체를 이용한 정렬" 항목에서 자세히 설명하겠습니다.

기본값으로 우선순위 큐는 오름차순으로 원소를 정렬합니다.

( 가장 높은 우선순위의 원소가 top에 위치합니다. )

 

예를 들어, int 데이터 타입의 우선순위 큐를 선언한다면 다음과 같습니다.

using namespace std;	// std 반복을 생략하기 위해서 namespace 선언

priority_queue<int> pq;	// int 타입 우선 순위 큐 선언

 

데이터의 입력 및 크기

push

void push( const Type& val );

우선순위 큐에 새로운 원소를 입력합니다.

이 원소는 원소가 가진 우선순위에 맞춰 자동으로 정렬됩니다.

 

size

우선순위 큐에 들어있는 원소의 개수를 반환합니다.

 

empty

우선순위 큐에 원소가 있는지 검사하는 함수입니다.

원소가 없으면 true를 반환합니다.

 

#include <iostream>
#include <queue>
using namespace std;

int main(){

    priority_queue<int> pq;

    pq.push(5); // 우선 순위 큐에 원소 입력
    pq.push(1);
    pq.push(3);
    pq.push(10);

    cout << pq.size();

    return 0;
}

 

데이터의 출력

top

const Type& top() const;

정렬 방식에 맞는 우선순위에 따라, 가장 높은 우선순위를 가진 데이터의 참조를 반환합니다.

만약, 정렬 방식을 내림차순으로 한다면, 가장 낮은 우선순위를 가진 데이터가 top 위치에 오게 될 것입니다.

우선순위 큐에 원소가 없는데, 이 함수가 호출되면 오류가 발생합니다.

pop

void pop();

top 위치에 있는 원소를 제거합니다.

원소 제거 시, 다음 높은 우선순위를 가진 원소가 자동으로 top이 됩니다.

 

top과 마찬가지로 우선순위 큐에 원소가 없는데, 이 함수가 호출되면 오류가 발생합니다.

empty 함수 등을 써서, 검사하는 과정이 필요합니다.

int main(){

    priority_queue<int> pq;

    pq.push(5); // 우선 순위 큐에 원소 입력
    pq.push(1);
    pq.push(3);
    pq.push(10);

    int cnt = pq.size();

    while( cnt > 0){
        cout << pq.top() << " ";    // 최상위 우선 순위를 출력

        pq.pop();
        cnt--;
    }

    return 0;
}

▼출력

10 5 3 1

 

비교 함수 객체를 이용한 정렬

우선순위 큐는 기본적으로 원소들을 오름차순으로 정렬합니다.

만약 우선순위를 내림차순으로 정렬하고자 하면 어떻게 해야 될까요?

 

이때, 사용자 정의 함수 객체를 사용할 수 있습니다.

여기서 T는 우선순위 큐의 데이터 타입입니다.

struct Compare{
    bool operator()( const T& a, const T& b) const{    
        return a > b;	// 내림차순으로 정렬
    }
};

이 함수에서 b가 a 보다 우선순위가 높다(오름차순)라고 설정하고자 하면 true를 반환하면 됩니다.

반대로 a가 b보다 우선순위가 높다라고 하고 싶으면 false를 반환합니다.

 

이전 항목의 예제를 내림차순으로 정렬하려면 다음과 같이 할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Compare{	// 사용자 함수 객체
    bool operator()( int a, int b){    // 내림차순으로 정렬
        return a > b;
    }
};

int main(){

    // 사용자 비교 함수 객체를 사용
    priority_queue<int, vector<int>, Compare> pq;

    pq.push(5); // 우선 순위 큐에 원소 입력
    pq.push(1);
    pq.push(3);
    pq.push(10);

    int cnt = pq.size();

    while( cnt > 0){
        cout << pq.top() << " ";    // 최상위 우선 순위를 출력

        pq.pop();
        cnt--;
    }

    return 0;
}

▼출력

1 3 5 10

위의 결과는 숫자 1이 top인 내림차순입니다.

 

그런데, 만약 우선순위 큐의 데이터 타입이 위의 예제처럼 int가 아니라 float 타입이면 

이와 같은 함수 객체를 또 만들어야 합니다.

그래서 C++에서는 이러한 함수 객체를 template 형태로 지원하고 있습니다.

template <class Type = void>
struct greater : public binary_function <Type, Type, bool>
{
    bool operator()(const Type& Left, const Type& Right) const;
};

여기서 Type은 operator >를 지원하는 모든 형식입니다.

이 객체를 사용해서 타입이 변경되더라도 같은 코드를 사용해서 내림차순으로 정렬할 수 있게 됩니다.

 

마찬가지로, 오름차순 정렬을 쉽게 하기 위한 less <Type> 객체도 제공합니다. 

이때, Type은 operator <를 지원하는 모든 형식입니다.

 

위 객체를 사용하면 위의 예제는 다음과 같이 변경할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){

    priority_queue<int, vector<int>, greater<int>> pq;  // 내림차순으로 정렬

    pq.push(5); // 우선 순위 큐에 원소 입력
    pq.push(1);
    pq.push(3);
    pq.push(10);

    int cnt = pq.size();

    while( cnt > 0){
        cout << pq.top() << " ";    // 최상위 우선 순위를 출력

        pq.pop();
        cnt--;
    }

    return 0;
}

▼출력

1 3 5 10

 

만약 float 형의 데이터를 내림차순으로 정렬하려면 greater <float> 객체를 사용하면 됩니다.

 

클래스의 우선순위

좀 더 복잡한 데이터는 어떻게 처리해야 할까요?
학생들의 기말고사 성적을 수학이 가장 높은 학생이 위로 오고, 같은 성적인 경우 한국사 성적을 높은 순으로 정렬하여 게시판에 공개한다고 가정을 해 봅시다.

 

여기서는 이러한 데이터를 우선순위 큐에 저장하여 정렬하는 방법을 알아보겠습니다.
 
우선 다양한 성적을 저장할 클래스가 필요합니다.

class cStudant{
public:
    cStudant(const string& str, int A, int B){
    	name = str; math = A; history = B;
    }

    string name;
    int math;
    int history;
};

 

그리고 클래스가 담고 있는 성적을 원하는 방식으로 정렬하는 함수 객체가 필요합니다.

정렬을 위한 사용자 비교 함수 객체는 다음과 같을 것입니다.

// 사용자 비교 함수 객체
struct Compare{
    bool operator()( const cStudant& A, const cStudant& B) const{
        
        if ( A.math == B.math){
            return A.history < B.history;
        }
        else{
            return A.math < B.math;
        }
    }
};

이 함수 객체는 수학 점수가 높으면 우선순위가 높고, 수학 점수가 같은 경우 역사 점수가 높으면 더 높은 우선순위를 부여합니다.

 

이제, 학생들의 데이터를 우선순위 큐에 입력하여 top 원소부터 출력하면, 원하는 대로 정렬된 순서를 얻을 수 있게 됩니다.

priority_queue< cStudant, vector<cStudant>, Compare > pq;

 

 

또 다른 방법으로는, CStudant 클래스의 operator를 정의하는 방법이 있습니다.

이 방식의 장점은 데이터의 우선순위를 결정하는 알고리즘을 클래스 내부로 감출 수 있고, 이전 항목에서 설명한 greater, less 함수 객체를 사용해 오름차순에서 내림차순으로 변경도 간단히 할 수 있습니다.

 

먼저, less 함수 객체(오름차순, 기본값)를 사용하기 위해선 클래스가 operator < 을 지원해야 합니다.

less 객체를 사용하지 않더라도, 우선순위 큐는 기본적으로 오름차순 정렬을 합니다.

그렇기 때문에 우선순위 큐 객체 선언 시, 사용자 함수 객체를 사용하거나 사용자 클래스에서 operator <를 지원해야 합니다. (컴파일이 되지 않습니다.)

bool operator < (const cStudant& other) const{
    if ( math == other.math){
        return history < other.history;
    }
    else{
        return math < other.math;
    }
}

 

greater 함수 객체(내림차순)를 사용하기 위해선 클래스가 operator >을 지원해야 합니다.

bool operator > (const cStudant& other) const {
    if ( math == other.math){
    	return history > other.history;
    }
    else{
    	return math > other.math;
    }
}

 

이제, 우선순위 큐에 데이터를 입력하고, top부터 출력하면 정렬된 순서의 데이터를 얻을 수 있습니다.

int main(){
    
    // less 객체를 사용해서 오름차순으로 정렬
    priority_queue<cStudant, vector<cStudant>, less<cStudant>> pq;

    pq.push( cStudant("A", 95, 98));  // 우선 순위 큐에 원소 입력
    pq.push( cStudant("B", 90, 85));
    pq.push( cStudant("C", 83, 80));
    pq.push( cStudant("D", 95, 92));
    pq.push( cStudant("E", 95, 95));
    
    int cnt = pq.size();

    while( cnt > 0){
        
        // 최상위 우선 순위를 출력
        cout << pq.top().name << " " << pq.top().math << " " << pq.top().history << endl;    

        pq.pop();
        cnt--;
    }

    return 0;
}

▼출력

A 95 98
E 95 95
D 95 92
B 90 85
C 83 80

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class cStudant{
public:
    cStudant(const string& str, int A, int B){
    	name = str; math = A; history = B;
    }

    string name;
    int math;
    int history;

    bool operator < (const cStudant& other) const{
        if ( math == other.math){
            return history < other.history;
        }
        else{
            return math < other.math;
        }
    }

    bool operator > (const cStudant& other) const {
        if ( math == other.math){
            return history > other.history;
        }
        else{
            return math > other.math;
        }
    }
};

// 사용자 비교 함수 객체
struct Compare{
    bool operator()( const cStudant& A, const cStudant& B) const{
        
        if ( A.math == B.math){
            return A.history < B.history;
        }
        else{
            return A.math < B.math;
        }
    }
};

int main(){

    // 사용자 함수 객체 사용
    //priority_queue<cStudant, vector<cStudant>, Compare> pq;  
    
    // less 함수 객체 사용
    priority_queue<cStudant, vector<cStudant>, less<cStudant>> pq;

    pq.push( cStudant("A", 95, 98));  // 우선 순위 큐에 원소 입력
    pq.push( cStudant("B", 90, 85));
    pq.push( cStudant("C", 83, 80));
    pq.push( cStudant("D", 95, 92));
    pq.push( cStudant("E", 95, 95));
    
    int cnt = pq.size();

    while( cnt > 0){

        // 최상위 우선 순위를 출력
        cout << pq.top().name << " " << pq.top().math << " " << pq.top().history << endl;    

        pq.pop();
        cnt--;
    }

    return 0;
}

 

 

저작자표시 비영리 변경금지

'C, C++ > 자료구조' 카테고리의 다른 글

[C++] STL map 사용법  (0) 2024.06.27
[C++] 덱 ( deque ) 사용법  (0) 2024.06.12
[C++] STL list 사용법  (0) 2024.06.11
[C++] STL Vector 사용법  (0) 2024.06.08
[C++] 반복자( Iterator )에 대한 설명과 종류  (0) 2024.06.06
  • 네이버 블로그 공유
  • 네이버 밴드 공유
  • 페이스북 공유
  • 카카오스토리 공유
C, C++/자료구조 관련 글
글 더보기

티스토리툴바