[Python] 우선순위 큐(Priority Queue) 활용법 - heapq 모듈과 예제 코드 살펴보기

우선순위 큐(Priority Queue)는 일반적인 큐(Queue)와 달리, 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다. 우선순위 큐는 작업 스케줄링, 네트워크 트래픽 제어, 이벤트 처리와 같이 작업을 우선순위에 따라 처리해야 할 때 유용합니다. 특히, 실시간 시스템이나 대기열 관리 시스템에서 많이 사용됩니다.그래프 알고리즘 등 다양한 분야에서 활용됩니다. 

파이썬에서는 heapq 모듈을 사용하여 우선순위 큐를 간단하게 구현할 수 있답니다.

 

우선순위 큐 구현의 장점

파이썬의 heapq 모듈을 사용한 우선순위 큐 구현의 장점은 다음과 같습니다:

1. 간단한 구현: heapq 모듈을 사용하여 몇 줄의 코드로 우선순위 큐를 구현할 수 있습니다.
2. 효율적인 연산: 삽입과 삭제 연산이 O(log n)의 시간 복잡도를 가지므로, 대량의 데이터를 처리할 때도 효율적입니다.
3. 기본 자료구조와의 호환성: 리스트를 기반으로 동작하므로, 파이썬의 기본 자료구조와 잘 어울립니다.

---

파이썬 우선순위 큐 예제 코드

다음은 heapq 모듈을 사용하여 우선순위 큐를 구현한 예제 코드입니다

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

# 예제 사용법
class Candy:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Candy({!r})'.format(self.name)

q = PriorityQueue()
q.push(Candy('롤리팝'), 1)
q.push(Candy('초콜릿'), 5)
q.push(Candy('젤리'), 4)
q.push(Candy('사탕'), 1)

print("첫 번째로 나온 캔디:", q.pop())  # 초콜릿
print("두 번째로 나온 캔디:", q.pop())  # 젤리
print("세 번째로 나온 캔디:", q.pop())  # 롤리팝 또는 사탕
print("네 번째로 나온 캔디:", q.pop())  # 사탕 또는 롤리팝

 

PriorityQueue 클래스의 push() 메서드를 사용하여 캔디와 우선순위를 큐에 삽입하고,

pop() 메서드를 사용하여 우선순위가 높은 캔디부터 꺼낼 수 있습니다.

우선순위 큐는 우선순위에 따라 데이터를 처리해야 할 때 유용하게 사용할 수 있습니다. 

예를 들어, 작업 스케줄러에서 우선순위가 높은 작업부터 처리하거나, 그래프 알고리즘에서 가중치가 낮은 간선부터 선택할 때 우선순위 큐를 활용할 수 있습니다.

 

---

FAQ

Q. 그러면 숫자가 높은게 우선순위가 높은걸까요?

A. 네, 맞습니다. 파이썬의 heapq 모듈은 최소 힙(min-heap)을 기반으로 동작하기 때문에, 우선순위를 음수로 변경하는 것이 최대 힙(max-heap) 기반의 우선순위 큐를 구현하는 일반적인 방법입니다. 위 코드에서는 우선순위에 음수를 취함으로써(-priority) 숫자가 높을수록 우선순위가 높아지도록 변경하였습니다. 

heapq 모듈은 가장 작은 값을 가진 항목을 루트로 유지하는 최소 힙을 제공합니다. 따라서 우선순위 값이 작을수록 우선순위가 높은 것으로 처리됩니다. 하지만 많은 경우, 우리는 우선순위 값이 클수록 우선순위가 높은 것으로 생각하는 것이 더 직관적입니다.

이러한 직관적인 방식으로 우선순위 큐를 사용하기 위해, 우선순위에 음수를 취하는 방법을 사용합니다. 예를 들어, 우선순위가 5인 항목은 -5로 변환되어 힙에 삽입됩니다. 이렇게 하면 heapq 모듈은 실제로는 가장 작은 값(-5)을 가진 항목을 루트로 유지하지만, 우리는 이를 우선순위가 가장 높은 항목(5)으로 해석할 수 있습니다.

이 방법은 파이썬 개발자들 사이에서 널리 사용되는 관용적인 방법이며, heapq 모듈의 동작 방식을 변경하지 않고도 최대 힙 기반의 우선순위 큐를 구현할 수 있는 간단하고 효과적인 방법이랍니다.

Q. 우선순위 큐에서 우선순위가 같은 항목들의 순서는 어떻게 정해지나요?

A. 우선순위가 같은 항목들의 순서는 삽입된 순서에 따라 결정됩니다. 위 코드에서는 self._index를 사용하여 삽입 순서를 추적하고 있습니다. 따라서 우선순위가 같은 경우, 먼저 삽입된 항목이 먼저 반환됩니다.

Q. 우선순위 큐에서 가장 우선순위가 높은 항목을 제거하지 않고 확인만 하고 싶은 경우에는 어떻게 해야 하나요?

A. heapq 모듈의 heapq.heappop() 함수는 가장 우선순위가 높은 항목을 제거하면서 반환합니다. 제거하지 않고 확인만 하고 싶다면 heapq.nsmallest(1, heap)[0][-1]을 사용하여 가장 우선순위가 높은 항목을 확인할 수 있습니다.

Q. 우선순위 큐에 이미 존재하는 항목의 우선순위를 변경하려면 어떻게 해야 하나요?

A. 파이썬의 heapq 모듈은 기본적으로 우선순위 변경 기능을 제공하지 않습니다. 따라서 우선순위를 변경하려면, 해당 항목을 제거한 후 새로운 우선순위로 다시 삽입해야 합니다. 이를 위해서는 항목을 고유하게 식별할 수 있는 방법이 필요합니다.

Q. 최대 힙(max-heap) 기반의 우선순위 큐를 구현하려면 어떻게 해야 하나요?

A. 파이썬의 heapq 모듈은 최소 힙(min-heap)을 기반으로 동작합니다. 최대 힙 기반의 우선순위 큐를 구현하려면, 우선순위에 음수를 취하는 방법을 사용할 수 있습니다. 위 코드에서는 (-priority, self._index, item)의 튜플을 사용하여 최대 힙 기반의 우선순위 큐를 구현하였습니다. 이렇게 하면 숫자가 높을수록 우선순위가 높아집니다.

 

---

여기까지, 우선순위 큐 구현에 대해 알아보았습니다. 

우리 모두 화이팅해요!

 

#파이썬우선순위큐
#heapq모듈
#우선순위큐구현
#파이썬자료구조
#파이썬알고리즘
#최소힙
#최대힙구현
#우선순위큐활용
#파이썬우선순위큐예제
#효율적인우선순위큐