[자료구조] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

들어간 순서에 상관없이 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조

 

• 스택 : 원소들은 후입 선출 순으로 처리된다. (LIFO; Last In First Out)
• 큐 : 원소들은 선입 선출 순으로 처리된다. (FIFO; First In First Out)

 

• 우선순위 큐를 구현하는 방법

1. List(리스트)  : 삽입 - O(1), 삭제 - O(N) 

2. Heap(힙) : 삽입 - O(logN), 삭제 - O(logN) 

 

 

우선순위 큐 import 및 생성

from queue import PriorityQueue

# 우선순위 큐 생성
que = PriorityQueue()

 

우선순위 큐 원소 추가 - .put()

que.put(1)
que.put(3)
que.put(8)
que.put(4)

 

우선순위 큐 원소 삭제 - .get()

que.get() # 1
que.get() # 3
que.get() # 4
que.get() # 8

 

우선순위 큐 정렬 기준 변경 - (우선순위, 값)의 튜플 형태

que.put((1, 'a'))
que.put((6, 'c'))
que.put((3, 'b'))
que.put((9, 'd'))

que.get()[1] # a
que.get()[1] # b
que.get()[1] # c
que.get()[1] # d