1. 우선순위 큐 (Priority Queue)
우선순위가 높은 요소가 먼저 제거되는 큐
-> 우선순위가 높은 요소가 먼저 나오는 구조
2. 우선순위 큐의 특징
- 우선순위가 높은 요소가 먼저 출력됨
- 동일한 우선순위가 있을 경우, 먼저 들어온 요소가 먼저 나옴
- 힙(Heap) 자료구조를 사용하여 구현하는 경우가 많음
3. 우선순위 큐의 구현 방식
우선순위 큐는 힙(Heap)을 이용하여 구현하는 것이 일반적
#최소 힙
import heapq
pq = [] # 우선순위 큐 생성
heapq.heappush(pq, 5) # 5 삽입
heapq.heappush(pq, 1) # 1 삽입
heapq.heappush(pq, 3) # 3 삽입
print(heapq.heappop(pq)) # 1 (최소값부터 제거)
print(heapq.heappop(pq)) # 3
print(heapq.heappop(pq)) # 5
#최대 힙
import heapq
pq = []
heapq.heappush(pq, -5) # 5를 -5로 변환하여 저장
heapq.heappush(pq, -1) # 1을 -1로 변환하여 저장
heapq.heappush(pq, -3) # 3을 -3로 변환하여 저장
print(-heapq.heappop(pq)) # 5 (가장 큰 값)
print(-heapq.heappop(pq)) # 3
print(-heapq.heappop(pq)) # 1
4. 시간복잡도
heappush() -> O(log N)
heappop() -> O(log N)
heapify() -> O(N) #힙으로 바꿔주는 연산
힙은 트리 기반 자료구조이므로,
삽입(heappush)과 삭제(heappop) 연산이 O(log N)으로 빠름.
5. 연습 문제
11279 - 최대 힙
1927 - 최소 힙
1715 - 카드 정렬하기
develog