python priority queue 예제 만들어줘

Python의 priority queue는 우선순위를 기준으로 항목을 정렬하여 꺼낼 수 있는 자료구조입니다. 일반적으로 heapq 모듈을 이용해 구현합니다. 아래에 예제를 단계별로 설명드릴게요.

🧱 Step-by-Step 예제: heapq로 우선순위 큐 만들기

✅ 1. heapq 모듈 소개

Python의 heapq는 min-heap 을 기반으로 합니다. 즉, 우선순위가 낮은 항목이 가장 먼저 나옵니다.

import heapq

✅ 2. 기본적인 우선순위 큐 예제 (숫자)

import heapq

# 빈 리스트를 힙으로 사용
pq = []

# 요소 추가 (heap push)
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)

# 우선순위가 가장 높은(가장 작은) 요소 꺼내기
while pq:
    print(heapq.heappop(pq))

출력:

1
3
5

✅ 3. 튜플을 활용한 우선순위 큐 (우선순위, 값)

import heapq

pq = []

# (우선순위, 값) 형태로 삽입
heapq.heappush(pq, (2, "청소"))
heapq.heappush(pq, (1, "공부"))
heapq.heappush(pq, (3, "게임"))

while pq:
    priority, task = heapq.heappop(pq)
    print(f"{task} (우선순위: {priority})")

출력:

scss

공부 (우선순위: 1)
청소 (우선순위: 2)
게임 (우선순위: 3)

✅ 4. 우선순위 큐 클래스로 추상화

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0  # 동일 우선순위 처리용

    def push(self, item, priority):
        # 우선순위 같을 때는 순서대로 처리하기 위해 index 사용
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1

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

# 사용 예시
pq = PriorityQueue()
pq.push("공부", 1)
pq.push("게임", 3)
pq.push("청소", 2)

while True:
    try:
        print(pq.pop())
    except IndexError:
        break

출력:

공부
청소
게임

필요하다면 최대 힙 , dict 기반 우선순위 큐 , 혹은 queue.PriorityQueue 클래스를 이용한 스레드 안전한 큐 예제도 제공해드릴 수 있어요. 원하시는 방향 있으신가요?

응 둘 다 해줘. 근데 queue.PriorityQueue는 많이 느렸던 것 같은 기억이 있는데 맞아?

좋은 질문이에요! 먼저 요청하신 두 가지 예제를 각각 설명드리고, 마지막에 queue.PriorityQueue의 성능 이슈에 대해서도 짚어드릴게요.

✅ 1. 최대 힙 (Max-Heap) 구현 방법

Python의 heapq는 min-heap 만 지원하므로, 우선순위가 클수록 먼저 나오는 최대 힙을 만들려면 우선순위를 음수로 변환 해야 합니다.

import heapq

class MaxHeap:
    def __init__(self):
        self._queue = []

    def push(self, item, priority):
        # priority를 음수로 바꿔서 최대 힙처럼 동작
        heapq.heappush(self._queue, (-priority, item))

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

# 사용 예시
pq = MaxHeap()
pq.push("공부", 1)
pq.push("게임", 3)
pq.push("청소", 2)

while pq._queue:
    print(pq.pop())

출력:

게임
청소
공부

✅ 2. queue.PriorityQueue를 이용한 예제 (스레드 안전)

queue.PriorityQueue는 스레드 안전(thread-safe) 한 큐입니다. heapq보다 상대적으로 느릴 수 있는데, 이유는 아래에 설명드릴게요.

from queue import PriorityQueue

pq = PriorityQueue()

pq.put((2, "청소"))
pq.put((1, "공부"))
pq.put((3, "게임"))

while not pq.empty():
    priority, task = pq.get()
    print(f"{task} (우선순위: {priority})")

출력:

scss

공부 (우선순위: 1)
청소 (우선순위: 2)
게임 (우선순위: 3)

⚠️ queue.PriorityQueue 성능 이슈에 대한 설명

queue.PriorityQueue가 느릴 수 있는 이유 는 다음과 같습니다:

  1. 스레드 안전 구현 :

    • 내부적으로 threading.Lock을 사용해 동시성 제어를 합니다.

    • 단일 스레드 환경에서는 불필요한 락(lock) 오버헤드가 생깁니다.

  2. 유연성 부족 :

    • 튜플 외에 커스텀 우선순위 로직을 넣기가 까다롭습니다.

    • heapq는 더 자유롭고 가볍습니다.

🟡 결론

  • 단일 스레드 / 빠른 작업 필요 : heapq 기반 구현 권장

  • 멀티스레드 환경 / 큐 안전성 필요 : queue.PriorityQueue 사용

원하신다면 heapq vs queue.PriorityQueue 성능 비교 실험 코드도 만들어드릴 수 있어요. 원하세요?

Categories:

Updated:

You may also enjoy