우선순위 큐

우선순위 큐는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다.

 

스택은 가장 나중에 삽입된 요소를 먼저 추출(LIFO), 큐는 가장 먼저 삽입된 요소를 먼저 추출(FIFO) 한다. 그러나 이와 달리 우선 순위 큐는 어떠한 특정 조건에따라 우선순위가 가장 높은 요소가 추출되는 자료형이다.

 

우선순위 큐

대표적으로 최댓값 추출을 들 수 있는데, 예를 들어 큐에 [1, 4, 5, 3, 2,] 가 들어 있고 최댓값을 추출하는 우선순위 큐가 있다고 가정하자 이 경우 항상 남아 있는 요소들의 최댓값이 우선순위에 따라 5, 4, 3, 2, 1 순으로 추출 된다.

 

이는 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수있다는 의미이기도 하다. n개의 요소를 결정하는데 S(n)의 시간이 소요된다고 할 때, 새 요소를 삽입하거나 요소를 삭제하는 데에는 O(S(n))의 시간이 소요된다.

반면 내림차순으로 정렬했을 때 최댓값을 가져오는데는 맨 앞의 값을 가져오기만 하면 되므로 O(1)로 가능하다. 대개 정렬로는 O(nlogn)이 필요하기 때문에 O(S(n))은 O(nlogn) 정도가 든다. 

 

파이썬은 대부분의 우선순위 큐 풀이에 거의 항상 heapq모듈을 사용한다. PriorityQueue 모듈도 있지만 heapq를 거의 사용한다.

파이썬의 PriorityQueue조차 내부적으로는 heapq를 사용하도록 구현되어있다. 

 

#cpython/Lib/queue.py

class PriorityQueue(Queue):

    ...

    def _put(self, item):

        heappush(self.queue, item)



    def _get(self):

        return heappop(self.queue)

 

이 코드에서 보듯이, PriorityQueue의 _get()과 _put()은 모두 headq 모듈의 heappop()과 heappush()를 그대로 사용하므로 사실상 둘은 동일 하다.

그렇다면 heapq와 PriorityQueue모듈의 차이점은 무엇일까?

차이점은 PriorityQueue는 스레드 세이프 클래스라는 점이며, heapq 모듈은 스레드세이프를 보장하지 않는다.

파이썬은 GIL의 특성상 멀티 스레딩이 거의 의미가 없기 때문에 대부분 멀티 프로세싱으로 활용한다는 점을 생각해보면, PriorityQueue 모듈의 멀티 스레딩 자원은 사실 큰 의미는 없다.

또한 스레드 세이프를 보장한다는 얘기는 내부적으로 Locking을 제공한다는 의미이므로 Locking Overhead가 발생해 성능에 영향을 끼친다.

따라서 굳이 멀티 스레도로 구현할 게 아니라면 PriorityQyeye 모듈은 사용할 필요가 없다.

또한 실무에서도 우선순위 큐는 대부분 heapq로 구현하고 있다.

 

Thread safe란?

Multi-Thread 에도 안전한 프로그래밍 개념.

만약 Thread safe 하지 않은 경우 1번 Thread의 값이 2번 Thread에서 변경될 수 있어 문제가 발생한다.