우선순위 큐(Queue)

우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다.

 

 

내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가집니다.

 

 

코드예시

from queue import PriorityQueue
que = PriorityQueue()
# que = PriorityQueue(maxsize=8) 디폴트사이즈는 무한대이다. 크기설정이 왼쪽과 같이하면 된다.

# 아래처럼 입력하면 오름차순으로 정렬이 된다.
que.put(4) # 원소추가
que.put(1)
que.put(7)
que.put(3) 

#정렬기준을 바꾸고 싶다면 아래처럼 하면된다.
# (우선순위, 값)의 형태로 저장할 수도 있음
que.put((5, 'FIVE'))
que.put((1, 'ONE'))
que.put((3, 'THREE'))

for _ in range(que.qsize()):
    print(que.get())
# 출력 결과
(1, 'ONE')
(3, 'THREE')
(5, 'FIVE')

for _ in range(que.qsize()):
    print(que.get()[1]
# 출력 결과
ONE
THREE
FIVE



que.qsize()    # 우선순위 큐의 크기 확인
que.empty()    # 우선순위 큐가 비어있는지 확인 
que.full()     # 우선순위 큐가 꽉 찼는지 확인

 

 

 

 

get()[1]의 의미?