🎱 Priority Queue
우선순위 큐(Priority Queue)는 우선순위가 높은 데이터에 집중하여, 우선순위가 높은 데이터먼저 나갈 수 있는 형태의 자료구조이다.
배열, 연결리스트 등으로도 구현 가능하지만, 힙(Heap)을 사용해야 삭제 시간을 O(logN)으로 최적화할 수 있다.
Python에는 PriorityQueue와 heapq를 통해 우선순위 큐를 이용할 수 있다.
둘에는 약간의 차이가 있는데, 오늘은 그중 heapq에 대해서 알아보자.
🎱 heapq
import heapq
pq = []
heapq.heapify(pq) # pq를 heapq화 함
heapq.heappush(pq, x) # pq에 데이터 추가
heapq.heappop(pq) # pq에서 가장 우선순위가 낮은 데이터 추출 및 반환총 6개의 메소드가 주를 이룬다.
특히, 새로운 자료구조를 형성하는 것이 아니라 기존의 자료구조(리스트)를 인자로 받아 사용함을 볼 수 있다.
⚽️ heapify
heapq.heapify가 눈에 띄는데, heapq.heapify는 빈 리스트에서 시작하지 않는 경우 사용할 수 있다.
예를 들어, 만약 초기 리스트에 값이 들어있는 경우에는 정렬 보장이 되지 않은 상태이기 때문에 여기서 heapq.heappush 또는 heapq.heappop 을 하게 되면 제대로 수행되지 않을 수 있다.
즉, 이미 들어있는 데이터를 heap정렬 시켜주는 역할이 되는거다.
heapq.heapify를 수행하면 해당 배열의 가장 첫번째 원소는 데이터가 가장 작은 값이 된다.
이 과정은 O(N)의 시간복잡도를 갖는다.
⚽️ heappush / heappop
heapq.heappush 와 heapq.heappop 은 각각 데이터를 넣고 빼는 역할이다.
참고로 대상 객체(pq)에 정렬이 되어 삽입되기 때문에 만약 가장 낮은 우선순위의 데이터를 추출하지 않고 확인만 하고싶다면(top), pq[0] 을 통해 확인 가능하다. 단, 주의해야할 점은 pq[0] 은 pq의 최솟값이 맞지만, pq[1], pq[2]등이 두번째로 작은 값, 세번째로 작은 값을 의미하지는 않는다. 즉 pq가 정렬된 객체는 아니라는 뜻이다.
top과 마찬가지로 size, empty등도 간단히 구현 가능하다.
| top | pq[0] |
|---|---|
| size | len(pq) |
| empty | not pq |
heapq.heappush 와 heapq.heappop 은 O(logN)의 시간복잡도를 갖는다.
⚽️ 높은 우선순위 정렬
여기서 설명을 통해 알 수 있듯이, heapq는 우선순위가 “낮은” 데이터에 집중한다.
이는 heapq가 min-heap을 사용하기 때문이다.
만약 우선순위가 “높은” 데이터를 찾고자 하는 경우라면, 삽입하는 데이터에 -를 붙여 부호를 변경해주어 쉽게 구현 가능하다.
이 경우, 데이터를 넣을 때 -를 붙여서 삽입하고 다시 뺄 때 -를 붙여서 사용해야함에 주의해야한다.
🎱 언제 사용할까?
우선순위가 있고 그에 따라 가장 큰 값이나 가장 작은 값을 찾고 싶다면 그냥 정렬을 통해 해결할 수 있다.
하지만 만약 값을 계속 삽입과 추출이 반복되는 상황에서는 매번 정렬을 수행하면 시간 복잡도가 증가하게 된다. (Python의 내장 정렬은 O(NlogN)의 시간복잡도를 갖는다.)
Priority Queue는 다음과 같은 경우 특히 효과적이다.
- 우선순위가 가장 높은/낮은 값에만 관심이 있다.
- 구조에서 값의 추가 삭제가 꾸준히 이루어짐에도 정렬이 필요하다.
위 두가지 특징이 눈에 띈다면 Priority Queue를 이용할 수 있겠다.
