파이썬 우선 순위 큐

 티스토리 

 

우선순위 큐(heapq) 사용하기

우선순위 큐는 데이터를 저장하고 추출할 때 항목들에 우선순위를 부여하여 관리하는 자료구조입니다. 파이썬에서는 heapq 모듈을 사용하여 우선순위 큐를 구현할 수 있습니다. 아래는 파이썬의 우선순위 큐에 대한 간단한 설명과 사용 예시입니다.

1. 코드리뷰

 

import heapq

# 우선순위 큐를 위한 리스트 변수 생성
priority_queue = []

# 항목 추가
heapq.heappush(priority_queue, (3, 'Code'))
heapq.heappush(priority_queue, (1, 'Cost'))
heapq.heappush(priority_queue, (2, 'Zero'))
heapq.heappush(priority_queue, (4, 'Life'))

# 항목 추출
while priority_queue:
    priority, item = heapq.heappop(priority_queue)
    print(f'Priority: {priority}, Item: {item}')

결과 :

Priority: 1, Item: Cost
Priority: 2, Item: Zero
Priority: 3, Item: Code
Priority: 4, Item: Life

 

우선순위 큐의 특징:

각 항목은 우선순위를 가지고 있으며, 이 우선순위에 따라 항목이 관리됩니다.
낮은 우선순위가 높은 우선순위보다 먼저 나옵니다. (오름차순)
heapq 모듈:

heapq 모듈은 최소 힙(min heap)을 제공하여 우선순위 큐를 구현합니다.
최소 힙은 가장 작은 값이 루트에 위치하며, 부모 노드의 값이 항상 자식 노드의 값보다 작습니다.
사용 예시:

우선순위 큐를 사용하려면 리스트를 힙으로 변환하고, heappush 및 heappop 함수를 사용하여 항목을 추가하거나 추출할 수 있습니다.

2. 코드 최적화 

 

최소 힙을 활용한 초기화:

heapq.heapify 함수를 사용하여 리스트를 최소 힙으로 초기화할 수 있습니다.

priority_queue = [(3, 'apple'), (1, 'banana'), (2, 'orange')]
heapq.heapify(priority_queue)

이렇게 하면 heappush 함수를 여러 번 호출하는 대신 리스트를 최소 힙으로 만들 수 있습니다.

수정한 코드 전체 내용

import heapq

# 최소 힙으로 초기화
priority_queue = [(3, 'apple'), (1, 'banana'), (2, 'orange')]
heapq.heapify(priority_queue)

# 항목 추출
while priority_queue:
    priority, item = heapq.heappop(priority_queue)
    print(f'Priority: {priority}, Item: {item}')

 

마무리

- 이번 포스팅은 파이썬 heapq 모듈을 활용한 우선순위 큐 에 대해 알아봤습니다.

 

궁금한 사항은 댓글을 통해서 남겨 주시면 답변 드리겠습니다.
감사합니다.