![[자료구조] 우선순위 큐 - Priority Queue](https://inblog.ai/_next/image?url=https%3A%2F%2Finblog.ai%2Fapi%2Fog%3Ftitle%3D%255B%25EC%259E%2590%25EB%25A3%258C%25EA%25B5%25AC%25EC%25A1%25B0%255D%2520%25EC%259A%25B0%25EC%2584%25A0%25EC%2588%259C%25EC%259C%2584%2520%25ED%2581%2590%2520-%2520Priority%2520Queue%26logoUrl%3Dhttps%253A%252F%252Finblog.ai%252Finblog_logo.png%26blogTitle%3D%25EB%25B0%25B1%25EC%2597%2594%25EB%2593%259C%25EB%25B8%2594%25EB%25A1%259C%25EA%25B7%25B8-dohyeong&w=1920&q=75)
우선순위 속성을 갖는 데이터의 삽입과 제거연산을 지원하는 ADT
우선순위 큐는 우선순위를 부여해서 큐에 삽입하고 가장 높은 우선순위를 가진 요소부터 빠져나오게 함
자료구조는 heap사용
힙은 최솟값(또는 최댓값)을 즉시 얻어낼 수 있게 한다는 점에서 우선순위 큐를 구현하는데 적합
python 라이브러리
from queue import PriorityQueue que = PriorityQueue() # 사이즈 제한 시 maxsize = n # put() 이용하여 원소를 추가 que.put(2) que.put(4) # 값을 오름차순으로 반환 que.get()
Priority Queue 와 Heapq 시간 속도 차이
- queue 라이브러리의 Priority Queue 를 보면 Heapq 를 사용하는 것을 알 수 있다
- 차이는 PriorityQueue는 Thread-Safe
- Heapq는 Non-safe
- Thread-Safe 하다는 건 반드시 확인 절차를 거쳐야 하기에 작업속도가 더 느리다.
→ 코딩 테스트시 Priority Queue 보다 Heapq 를 사용하는게 더 빠르다
Share article