자료구조 및 알고리즘 자료 Priority Queue

1. Definition

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 갖고 있는 특별한 형태의 큐이다. 일반적인 큐는 선입선출(FIFO) 방식으로 동작하는 반면, 우선순위 큐는 요소들이 삽입된 순서가 아니라 각 요소의 우선순위에 따라 처리된다. 즉, 우선순위가 높은 요소가 먼저 제거되며, 동일한 우선순위를 가진 요소들은 일반적으로 먼저 들어온 순서대로 처리된다. 이러한 특성 때문에 우선순위 큐는 다양한 응용 프로그램과 알고리즘에서 아주 유용하게 사용된다. 우선순위 큐의 기본 연산은 삽입(insert), 제거(remove), 그리고 최상위 요소 접근(peek)을 포함한다. 삽입 연산은 큐에 요소를 추가하며, 이때 해당 요소의 우선순위도 함께 지정된다. 제거 연산은 가장 높은 우선순위를 가진 요소를 큐에서 제거하고 이 요소를 반환한다. 최상위 요소 접근 연산은 큐 구조에서 가장 높은 우선순위를 가진 요소를 제거하지 않고 확인할 수 있게 해준다. 이러한 연산들은 보통 O(log n) 또는 O(시간 복잡도를 가지며, 구현에 따라 다소 차이가 있을 수 있다. 우선순위 큐는 다양한 데이터 구조를 통해 구현할 수 있다. 일반적으로는 힙(heap) 구조를 사용하여 구현되…