
[python] 우선순위 큐 PriorityQueue VS heapq
·
python
⭐️ 1. 우선순위 큐?우선순위가 높은 데이터가 먼저 나가는 (제일 위에 놓임) 큐즉, 제일 첫번째 원소가 제일 우선순위가 높은 것 구현 방식- Heap, List, ... 등 구현 방식이 있다. 시간복잡도에 차이가 존재한다.List의 경우삽입: O(1), 삭제: O(N) Heap의 경우삽입: O(logN), 삭제:O(logN) ✅ 사용 예시- 스케줄링, 사건 시뮬레이션, 우선순위에 따른 검색, 정렬 등 ✅ 규칙 (최소 힙 기준)부모가 두 자식보다 더 작은 수임이 보장된다. (부모가 min)완전 이진 트리를 만족한다. ✅ 동작 (회소 힙 기준)추가 (push) 동작- 맨 마지막 원소로 추가한다- 해당 위치에서 root까지 순회하며, min heap을 만족하는지 체크한다 시간복잡도: O(logN) 삭제..