[파이썬] 우선순위큐(PriorityQueue) 사용법

Queue는 FIFO(Fist in First Out) 자료구조입니다.

FIFO에서는 처음에  추가된 아이템이 처음으로 빠져나옵니다.

Queue

우선순위큐는 큐의 스페셜 타입입니다.

큐는 큐인데 조금 더 특별한 기능(우선순위)을 제공하는 큐라고 생각합니다.

 

큐는 FIFO이지만, 우선순위큐는 우선순위 기반해서 아이템이 제거됩니다. 즉, 최고 우선순위를 가진 아이템이 먼저 제거됩니다. 우선순위큐의 put(), get() 함수는 O(nlogn) 시간복잡도를 갖습니다.

 

우선순위큐 아이템 제거

 

 

 

사용법1) put(), get()

PriorityQueue 객체를 생성하고 put()으로 아이템을 넣으면 내부적으로 오름차순 정렬을 합니다.

get() 함수를 통해서 원소를 가져옵니다.

from queue import PriorityQueue

# 우선순위 큐 객체 생성
q = PriorityQueue()

# 숫자 아이템 추가
q.put(5)
q.put(1)
q.put(10)
q.put(8)
q.put(3)

while not q.empty():
    print(q.get(), end=' ')

출력

1 3 5 8 10 

사용법2) tuple 오브젝트 저장

우선순유큐는 tuples처럼 오브젝트도 저장할 수 있습니다.

from queue import PriorityQueue

# 우선순위 큐 객체 생성
q = PriorityQueue()

# 튜플 객체 저장
q.put((20, 'james'))
q.put((49, 'adele'))
q.put((15, 'jack'))
q.put((30, 'michael'))

while not q.empty():
    print(q.get(), end=' ')

출력

(15, 'jack') (20, 'james') (30, 'michael') (49, 'adele') 

사용법3) 클래스 및 대소비교 함수

우선순위 큐에 클래스도 put() 할 수 있습니다.

클래스 내부에는 대소비교 함수 __lt__()를 구현해야 합니다.

lt는 less than의 약어입니다. 우선순위 큐는 내부적으로 __lt__()를 호출해서 대소비교를 합니다.

from queue import PriorityQueue

class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age
        
    # 대소 비교 메소드 구현
    def __lt__(self, other):
        return self.age < other.age
    
# 우선순위 큐 객체 생성
q = PriorityQueue()

# 학생 객체 생성 및 추가
# 학색 클래스의 __lt__(대소비교메소드)를 통해서 age 오름차순 정렬이된다.
q.put(Student('kyle', 22))
q.put(Student('gupy', 21))
q.put(Student('adele', 22))
q.put(Student('melo', 26))
q.put(Student('jack', 22))

while not q.empty():
    student = q.get()
    print(student.name, student.age)

출력

gupy 21
adele 22
jack 22
kyle 22
melo 26