우선순위 큐 - PriorityQueue, heapq

PriorityQueue

우선순위 큐는 데이터를 추가한 순서와 상관없이 데이터를 꺼낼 때 오름차순으로 반환함

 

from queue import PriorityQueue
queue = PriorityQueue()
queue = PriorityQueue(maxsize = 10) # 사이즈 제한

# 원소 추가
queue.put(data)

# 원소 제거
queue.get()

# 크기 확인
queue.qsize()

# 비어있는지 확인
queue.empty() # True or False

# 가득찼는지 확인
queue.full() # True or False

 

 

heapq

리스트를 최소 힙으로 사용하여 리스트의 첫 번째 요소가 항상 최소값을 가지도록 유지된다.

이진트리 기반 최소 힙을 제공하여 우선순위 큐를 간단하게 구현 할 수 있다.

 

*이진트리는 부모 노드가 항상 자식 노드보다 작은 값을 가지도록 정렬된 자료구조이다.

 

import heapq

heap = [] # 우선순위 큐 생성

# 항목 추가
heapq.heappush(heap, 5) 
heapq.heappush(heap, 2)
heapq.heappush(heap, 10)

# 최소값 출력 및 제거
heapq.heappop(heap) # 2

# n개의 가장 작은 항목들을 리스트로 반환
heapq.nsmallest(1, heap) # 5

# n개의 가장 큰 항목들을 리스트로 반환
heapq.nlargest(1, heap) # 10

arr = [5, 2, 3, 1]
# 최소 힙 변환
heapq.heapify(arr) # [1, 2, 3, 5]