[자료구조] 8. 우선순위 큐(Priority queue)

우선순위 큐에 대해 소개하기 전에 ADT(Abstract Data Type)와 implementation(구현 방법)의 차이에 대해서 잠시 다시 짚어보겠습니다.

ADT(자료구조)	Implementation(구현 방법)
List	Array, Linked list
Stack	Array, Linked list
Queue	Array, Linked list
Tree	Linked structure
Binary tree	Array, Linked structure
Priority queue	Heap, Binary search tree, List

위와 같이 각 자료구조는 여러가지의 구현 방법이 있을 수 있습니다. 또한 다른 자료구조 자체도 다른 자료구조의 구현 방법이 될 수 있습니다. 이를 여기서 다시 짚어보는 이유는 우선순위 큐의 개념을 이론적으로 설명하기 위해 우선순위 큐를 리스트로 구현해볼 것이기 때문입니다.

우선 리스트로 구현해보는 이유는, 실제로 우선순위 큐를 만들때는 힙을 사용하는 것이 보통이여서 우선순위 큐와 힙의 차이를 모르거나 햇갈리고, 우선순위 큐와 힙을 동일한 것으로 이해하는 경우가 있기 때문입니다. 그렇기에 단지 힙은 우선순위 큐의 한 구현 방식일 뿐인것을 보여주기 위해 리스트로 구현해보도록 하겠습니다.

우선순위 큐(Priority queue)

우선순위 큐는 무작위 수를 입력받고, 이를 출력할때 정해진 규칙에 따라 우선순위가 높은것 순으로 내보냅니다. 이때 이런 규칙을 비교자로 정하게 됩니다.

예시를 들자면 흔히 사용하는 최소-힙(min-heap)은 가장 작은 수를 내보낸다는 규칙을 가지고 있는 것입니다.

비교자(Compartor)

비교자에 대해 알아보기 전에 Total order relation과 Partital order relation에 대해 소개하겠습니다.

Total order relation

우선순위를 비교하려면 비교규칙(<=)가 항상 적용되는 total order을 만족해야합니다.

Total order relation은 집합론적 개념인데, 집합 S에 대해서 두 원소의 관계가 Total order relation을 가지려면 다음 3가지 속성을 만족해야 합니다.

1. 반사성(Reflexivity property): x <= x
2. 반대 대칭성(Antisymmetry property): x <= y 그리고 y <= x 라면 x == y
3. 추이성(Transitivity property): x <= y 그리고 y <= z 라면 x <= z

우리가 흔히 생각하는 일반적인 규칙과 다르지 않습니다.

Partitial order relation

Total order relation과 비슷하나, 모든 원소에 대해 비교 가능함을 보장하지 않는다.

비교자 구현체

다음은 C++에서 구현된 비교자의 예시입니다.

struct compare {
    // bigger value -> get higher priority
    bool operator()(const int &e1, const int &e2) const { return e1 > e2; }
};

내부의 규칙을 변경하여 다양한 규칙을 적용할 수 있습니다. 이런식의 비교자는 우선순위 큐 뿐만 아니라 정렬 함수등에서도 정렬 기준을 정할 때 사용할 수 있습니다.

---

활용

우선순위 큐는 다양한 알고리즘 문제 풀이에서 사용됩니다.

Priority Queue Sorting

우선순위에 따라서 반환해준다는 특성을 이용하면 모든 원소를 우선순위 큐에 삽입한후 모두 꺼내면 정렬된 상태의 데이터를 얻을 수 있습니다.

Heap Sort(힙 정렬)

이때 우선순위 큐의 구현에 heap을 사용하면 시간복잡도는 O(nlogn)인데, 이러한 정렬방식을 heap sort라고 합니다.

Selection Sort(선택 정렬)

우선순위 큐의 구현을 unsorted list 방식으로 한다면, 이를 이용한 정렬은 selection sort와 같은 방식입니다.

Selection sort의 방식은 정렬되지 않는 배열을 계속 순환하며 최소값을 찾아서 선택하고 이를 정렬된 배열에 차례대로 추가하는 방식입니다. 즉 정렬되지 않는 배열(unsorted list)에서 지속적으로 최소값을 찾아내서 정렬된 배열으로 만드는 과정과 동일하다 할 수 있습니다.

둘의 시간복잡도도 O(n^2)으로 동일합니다.

Insertion Sort(삽입 정렬)

우선순위 큐의 구현을 sorted list 방식으로 한다면, 이를 이용한 정렬은 insertion sort와 같은 방식입니다.

Insertion sort의 방식은 정렬되지 않는 배열에서 아무 원소를 골라 정렬된 배열의 적절한 위치에 삽입하는 방식입니다. 즉 정렬된 배열(sorted list)를 만들때 원소를 추가하면 적절한 위치에 삽입되기에 insertion sort와 동일하다고 할 수 있습니다.

둘의 시간복잡도도 O(n^2)으로 동일합니다.

---

우선순위 큐의 ADT

int getSize()
bool isEmpty()

우선순위 큐는 우선순위에 따라서 반환해주는 '큐' 이기에 enqueue와 dequeue를 가지는 큐와 비슷한 ADT를 가집니다.

// typename T
void insert(T& element): 원소를 삽입
T& remove(): 가장 우선순위가 높은 값을 반환하고 삭제
T& find(): 가장 우선순위가 높은 값을 반환

---

구현

리스트 기반 우선순위 큐(List based priority queue)

리스트로 구현한 우선순위큐는 insert와 remove를 합쳐서 O(n)의 시간복잡도를 보이기에, 주로 사용되지는 않습니다. 다만 insert나 remove 둘중 하나만 O(n)이고 다른 하나는 O(1)이니 특정 경우에는 효율적으로 사용될 수 있습니다.

unsorted list

insert시에 배열에 그냥 삽입하고, remove시에 값을 찾는 방식입니다. 각각 O(1)과 O(n)이 들어 최종적으로 O(n)이 소요됩니다.

sorted list

insert시에 배열에 정렬하여 삽입하고, remove시에 바로 반환하는 방식입니다. 각각 O(n)과 O(1)이 들어 최종적으로 O(n)이 소요됩니다.

정렬

이렇게 리스트 기반으로 우선순위 큐를 만들어 이를 이용해 정렬을 한다면, 모든 원소 수 n에 대하여 O(n)을 시행하게 되어 총 O(n^2)의 비효율적인 정렬이 됩니다.

힙 기반 우선순위 큐(Heap based priority queue)

실제로 자주 사용되는 방식의 구현입니다. 힙의 특성으로 인해 insert와 remove모두 O(log n)의 시간복잡도를 가집니다. 이에 대한 자세한 내용은 다음 포스트 '힙(Heap)'에서 알아보겠습니다.

이진 탐색트리 기반 우선순위 큐(Binary search tree based priority queue)

이진 탐색트리도 O(h), 즉 최적화시에 O(log n)에 가능하지만 사용되지는 않습니다. 이유는 최적화를 위해 AVL Tree등을 사용하면 구현이 어렵고, 최적화시의 비효율로 인하여 힙보다 실질적인 효율은 더 떨어지기 때문입니다.

---

효율

	unsorted list	sorted list	heap
insert()	O(1)	O(n)	O(log n)
remove()	O(n)	O(1)	O(log n)

구현 방식에 따라 위와 같은 시간복잡도를 가지게 됩니다.