[python] 우선순위 큐 PriorityQueue

import

from queue import PriorityQueue

생성 및 초기화

pq = PriorityQueue()

크기 지정 
fixed_pq = PriorityQueue(maxsize=256)

원소 추가

pq.put(1)
pq.put(2)
pq.put(3)

원소 삭제(반환하며 삭제함)

value = pq.get()

원소 개수 구하기

size = pq.qsize()

정렬 기준 커스터마이징

튜플이 형태로 맨앞 원소에 우선순위를 부여하면 된다.

pq.put((1, "Hi"))
pq.put((2, "Oh. Hi!"))

pq.get()[1]

객체 정렬하기

기본적으로 객체는 비교가 불가능하다. 그래서 객체의 내부에 비교를 위한 메서드를 추가한다.

==	__eq__
!=	__ne__
<	__lt__
<=	__le__
>	__gt__
>=	__ge__

class Car:
    def __init__(self, created_date):
        self.created_date = created_date

    def __lt__(self,other): 
        return self.created_date < other.created_date 

이외 empty, full 여부 등을 구할 수 있는 empty(), full(), 비동기를 지원하기에 관련된 join() 같은 API가 있다.

삽입과 제거에 O(logN)의 시간이 소요됨으로 최초에 N개의 원소로 우선순위를 만들게되면 0(NlogN)의 시간이 소요된다.

최소값을 찾는 알고리즘에는 이미 완성된 구조에서 0(N)의 시간으로도 구할 수 있지만 PriorityQueue를 사용하면 O(logN)에 구할 수 있다.

최소값을 하나 빼내고 나서도 특성상 다음 최소값을 나타내기에 반복적으로 최소값을 구하는 상황에서 유리하다. 다익스트라나 그리디 문제에서 자주 볼 수 있었다.

PriorityQueue에서는 최소값을 구하긴 편해도 최대값을 구하기에는 불편함이 크다. (저장할 때 우선순위를 음수를 곱하고, 비교 후 꺼낼 때 다시 음수를 곱하여 복구) PriorityQueue말고도 Heapq가 있는데 이게 일반적으로 좀 더 빠르다한다.

읽어주셔서 감사합니다.