우선순위 큐 (Priority Queue)

사진 출처 : 링크

우리가 생각하는 큐는 FIFO(First In First Out)의 자료구조로 먼저 들어간 데이터가 먼저 나온다. 우선순위 큐도 큐이다. 하지만, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다. 예를 들어 설명하려 한다.

(Ex) 병원의 응급실을 생각해보자. 모든 환자분들이 빠른 치료를 받고 완치가 되면 좋겠지만, 제일 응급한 환자부터 치료를 하게 된다. 즉, 우선순위가 높은 환자부터 먼저 치료를 받게 되는 것이다.

• 우선순위 큐는 평범한 스택, 큐와 비슷한 축약 자료형이다.

• 각 원소들은 우선순위를 가지고 있다. 따라서 높은 우선순위를 가진 원소가 먼저 처리된다.
  만약 같은 우선순위를 가진 원소가 있다면, 원소의 순서에 따라 처리된다.

우선순위 큐(Priority Queue)의 구현

우선순위 큐를 구현하는 방법은 3가지로 나뉘어진다. (우선순위 큐가 힙이라는 것은 오류이다. 배열, 연결리스트, 힙을 이용하여 다양하게 구현할 수 있다.)

1. 배열 기반 우선순위 큐

2. 연결리스트 기반 우선순위 큐

3. 힙(Heap) 기반 우선순위 큐 (힙 자료구조 설명은 여기에)

3가지의 방법으로 구현한 우선순위 큐의 성능은 아래의 표와 같다.

구현 방법	데이터 삽입	데이터 삭제
배열 기반	O(N)	O(1)
연결리스트 기반	O(N)	O(1)
힙 기반	O(logN)	O(logN)

배열 or 연결리스트 기반 우선순위 큐를 구현할 경우 간단하게 구현이 가능하다. 하지만, 배열 or 연결리스트를 이용하여 우선순위 큐를 만들게되면 단점이 있다.

• 배열 기반
  • 데이터 삽입, 삭제 과정에서 데이터를 1칸씩 당기거나 미는 연산을 계속 해야한다. 그리고 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야하는 단점이 있다. 이 경우는 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생하는 최악의 경우이다. (모든 배열을 탐색해야하는 경우이다.) (삭제는 O(1) , 삽입은 O(N))
• 연결리스트 기반
  • 연결리스트 또한 데이터 삽입, 삭제 과정에서 해당 위치를 찾아야한다. 최악의 경우에는 모든 연결리스트를 탐색해야한다. (삭제는 O(1) , 삽입은 O(N))

이처럼 배열 or 연결리스트 기반 우선순위 큐가 데이터 삭제 과정에서는 힙 기반 우선순위 큐보다 성능이 좋다. 하지만, 데이터 삽입 과정에서의 시간복잡도가 월등하기 때문에 일반적으로 힙 기반으로 우선순위 큐를 구현한다.

Python에서 우선순위 큐 사용하기

Python에서는 PriorityQueue와 heapq 모듈을 지원한다.
코딩 테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 heapq 모듈을 통한 우선순위 큐의 사용을 권장한다. 또한, 힙 기반 우선순위 큐를 이용할때 Python에서 힙은 최소 힙(Min Heap)으로 구성되어 있다. 힙에 넣었다가 빼면 오름차순 정렬이 기본적으로 수행된다.

PriorityQueue

from queue import PriorityQueue

q = PriorityQueue()

q.put(1)
q.put(10)
q.put(100)

q.get()
>>> 1
q.get()
>>> 10
q.get()
>>> 100

heapq

import heapq

q = []

heapq.heappush(q, 1)
heapq.heappush(q, 10)
heapq.heappush(q, 100)

heapq.heappop(q)
>>> 1
heapq.heappop(q)
>>> 10
heapq.heappop(q)
>>> 100

그러면 PriorityQueue 모듈과 heapq의 차이는 무엇일까? 어떤 것을 써야될까? 라는 생각이 들 수 있다. 먼저 PriorityQueue는 객체, heapq는 여러 함수들이 있는 파일이라고 한다. (정확한 정보는 아니다!)

PriorityQueue 모듈의 메소드들은 heapq에 비해 사용빈도가 낮고 쓰기가 힘들다. 그리고 PriorityQueue는 lock을 제공하여 thread-safe class 이고, 완벽한 정렬을 제공한다.

하지만 heapq는 리스트를 사용하기 때문에 thread-safe class 가 아니고, 느슨한 정렬을 제공한다. 두 모듈은 이러한 차이점이 있다고 한다. 위에 말했듯이 코딩 테스트 환경에서는 더 빠른 heapq 모듈을 사용하자!