[알고리즘] ep1-1) 우선순위 큐

ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐

요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다

각 항목은 (key, value)쌍을 갖는다

 

활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등

 

 

[구현 방법 2가지]

1. 리스트를 이용한 구현

① 무순리스트로 구현: 리스트에 임의 순서로 저장

e.g. 선택정렬

"unstable"

 

 

② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장

e.g. 삽입정렬

"stable"

 

 

 

2. 힙을 이용한 구현

① 최대 힙 사용

② 최소 힙 사용

 

 

시간 복잡도 비교

 

일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙)

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan), 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약(유튜브 동빈나)