[자료구조] 우선순위 큐

우선순위 큐

: 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입

저장된 원소들 중 가장 우선순위가 높은 원소가 삭제됨

 

키

응용프로그램에서는 종종 "키"라고 불리는 매개변수 또는 특성에 따라 객체들을 비교하고 순위를 매기는 것이 필요하다. 여기서 키는 집합에 포함된 각 객체에 주어진 값이다. 공식적으로, 우리는 키를 원소들에게 속성으로 주어진 객체라고 정의하며 그 원소를 식별하거나 순위를 정하거나 측정하는 데 사용된다.

 

비교자(Comparator)

우선순위 큐의 구현에 있어 중요한 점은 키를 비교하기 위한 관계를 정의하는 방법이다.

일반적인 접근방법은 우선순위 큐를 템플릿화된 클래스로 가정하는 것이다. 우리는 우선순위 큐의 원소로 사용될 수 있는 각 클래스가 타입 E를 갖는 두 개의 객체를 비교할 수 있는 수단을 제공한다고 가정한다. 타입 E를 갖는 각 객체가 comp라는 함수를 제공하여 두 객체를 비교하고 어떤 것이 큰지 결정할 수 있다. 프로그래머가 타입 E를 갖는 객체들에 대해 함수를 정의하여 이것이 비교 연산자 "<"를 덮어쓰는 것이다. C++ 용어로 이것을 함수 객체(function object)라 한다.

 

클래스 Point2D가 이차원 점을 정의한다고 가정하자. 이것은 x와 y 좌표값에 각각 접근하는 public 멤버 함수 getX()와 getY()를 가진다. 우리는 사전 순서로 "작다" 연산자를 다음과 같이 정의할 수 있다. 만약 x 좌표값이 다르면 그들의 상대값을 사용하고, 그렇지 않으면 y 좌표의 상대값을 사용한다.

bool operator<(const Point2D& p, const Point2D& q) {
    if (p.getX() == q.getX())	
    	return p.getY() < q.getY();
    else
    	return p.getX() < q.getX();
}

이 방법은 같은 타입의 객체들은 항상 같은 방법으로 비교한다는 가정하에 만든 것이다. 그러나 어떤 경우에는 같은 타입의 객체들을 여러 가지 방법으로 비교할 수 있다!!

class LeftRight {	// 왼쪽-오른쪽 비교자
public:
    bool operator()(const Point2D& p, const Point2D& q) const {
    	return p.getX() < q.getX();
    }
};

class BottomTop {	// 아래-위 비교자
public:
    bool operator()(const Point2D& p, const Point2D &q) const {
    	return p.getY() < q.getY();
    }
};

원소들에 대해 비교자가 주어졌을 때 두 원소 중 작은 것을 출력하는 함수를 정의하자!!

 

template <typename E, typename C>	// 원소 타입과 비교자
void printSmaller(const E& p, const E& q, const C& isLess) {
	cout << (isLess(p, q) ? p : 1) << endl;	// p와 q 중 작은 것을 출력
}

 

마지막으로 두 점에 우리 함수를 어떻게 적용하는지를 살펴보자.

Point2D p(1.3, 5.7), q(2.5, 0.6);	// 두 점
LeftRight leftRight;	// 왼쪽-오른쪽 비교자
BottomTop bottomTop;	// 아래-위 비교자
printSmaller(p, q, leftRight);	// output: (1.3, 5.7)
pritnSmaller(p, q, bottomTop);	// output: (2.5, 0.6)

주어진 비교자에 따라, 함수 pritnSmaller 내의 함수 isLess는 LeftRight 또는 BottomTop 클래스의 "()" 연산자를 호출한다. 이와 같은 방법으로, 우리는 같은 이차원 점 클래스에 대해 서로 다른 행동을 하는 결과를 얻을 수 있다.

 

비교자 사용을 통해, 프로그래머는 다양한 상황에서 이용할 수 있는 일반적인 우선순위 큐를 구현할 수 있다. 우선순위 큐는 원소 E와 비교자 C에 의해 템플릿화된 일반 클래스이다.

비교자 접근법은 구성 방법(composition method)보다 덜 일반적이다. 그 이유는 비교자가 원소 자신들의 내용에 대한 판단을 기반으로 하기 때문이다. 구성 방법에서는 키가 원소 객체의 일부분이 아닌 정보를 포함할 수 있다. 비교자 접근법은 원소-키 쌍을 생성할 필요 없이 원소를 우선순위 큐에 직접 삽입할 수 있기 때문에 더 간단하다는 장점을 갖는다.

 

우선순위 큐를 이용한 정렬

우선순위 큐 P는 다음 함수를 지원한다.

• size(): P에 있는 원소 개수 반환
• empty(): P가 비어있으면 true, 아니면 false
• insert(e): 새 원소 e를 P에 삽입
• min(): P에서 가장 작은 키를 갖는 원소 e의 레퍼런스 반환
• removeMin(): 함수 min()에 의해 레퍼런스되는 원소를 P에서 삭제

비교될 수 있는 n개 원소들의 집합 L이 주어졌을 때, 이들을 오름차순(같은 것이 있다면 비내림차순)으로 정렬하려고 한다. L을 우선순위 큐 Q를 이용하여 정렬하는 알고리즘을 PriorityQueueSort라 부른다!

다음 두 단계로 이루어진다.

1. 처음에 비어있는 우선순위 큐 P에 L의 원소들을 n번의 연속된 insertItem() 연산에 의하여 한 원소에 대해 하나의 연산으로 삽입한다.
2. n번의 연속된 min과 removeMin 연산을 이용하여 P에서 각 원소를 비내림차순으로 하나씩 꺼내어 L에 다시 넣는다.

Algorithm PriorityQueueSort(L, P):
    input: n개의 원소를 저장하는 리스트 L, 전체 순서 관계를 이용해 키를 비교하는 우선순위 큐 P
    output: 정렬된 리스트 L
    
    while !L.empty() do
    	e <- L.front
        L.pop_front()	리스트에서 한 원소 e를 삭제
        P.insert(e)		우선순위 큐에 삽입
    while !P.empty() do
    	e <- P.min()
        P.removeMin()	P에서 가장 작은 원소 e를 삭제
        L.push_back(e)	삭제된 원소를 L의 끝에 추가

 

리스트를 이용한 우선순위 큐의 구현

template <typename E, typename C>
class ListPriorityQueue {
public:
    int size() const {	// 원소의 개수
    	return L.size();
    }
    bool empty() const {	// 큐가 비었는지
    	return L.empty();
    }
    void insert(const E& e) {	// 원소 삽입
    	typename std::list<E>:: iterator p;
        p = L.begin();
        while (p != L.end() && !isLess(e, *p)) p++	// 더 큰 원소 검색
        L.insert(p, e);	// p앞에 e 삽입
    }
    const E& min() const {	// 최소 원소
    	return L.front();
    }
    void removeMin() {	//	최소 원소 삭제
    	L.pop_front();
    }
private:
   std::list<E> L;	// 우선순위 큐의 내용
   C isLess;	// less-than 비교자

원소 e를 우선순위 큐에 삽입하기 위해 e의 키값보다 큰 키를 갖는 첫 번째 원소를 찾을 때 까지 리스트를 차례로 탐색한 다음 p의 바로 앞에 e를 삽입한다. *p로 p가 레퍼런스하는 원소에 접근하고 ++p는 리스트의 다음 원소로 이동한다.

 

선택 정렬

1. S->P (O(n)시간 걸림)
2. P에서 removeMin 연산을 하여 P->S (O(n^2) 시간 걸림)

=> O(n^2)

 

삽입 정렬

1. S에서 원소를 P에 넣는데 삽입할 때 원소의 적절한 위치를 찾을 때 까지 탐색 (O(n^2))
2. P->S (O(n))

선택 정렬은 첫 번째 단계에서는 빠르지만 두 번째 단계에서 느린 반면, 삽입 정렬은 첫 번째 단계에서 느리지만 두 번째 단계에서 빨리 실행한다. 이 두 단계의 실행시간을 균형있게 만들 수 있다면, 전체 정렬 시간을 단축할 수 있다! 우선순위 큐를 효율적으로 구현하기 위해서 힙(heap)이라는 자료구조를 이용한다. 얘는 다음 포스팅!!!

---

참고 문헌

[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.