우선순위 큐(Priority Queue)란?

**우선순위 큐(Priority Queue)**는 일반적인 큐(Queue)와 비슷한 자료 구조이지만, 데이터의 우선순위에 따라 요소를 삽입하고 제거하는 특징을 가집니다. 즉, 큐에서 요소가 제거될 때 가장 높은 우선순위를 가진 요소가 먼저 나가는 구조입니다.

1. 우선순위 큐의 특징

• 우선순위 기반 요소 제거:
  • 일반적인 큐는 FIFO(First-In-First-Out) 방식으로, 먼저 들어온 데이터가 먼저 나가는 반면, 우선순위 큐는 각 요소에 우선순위를 부여하고, 가장 높은 우선순위를 가진 요소가 먼저 제거됩니다.
• 삽입과 삭제 연산의 효율성:
  • 우선순위 큐는 효율적으로 삽입과 삭제 연산을 수행할 수 있도록 구현됩니다. 일반적으로 힙(Heap) 자료 구조를 사용하여 구현하는 경우가 많습니다.
• 두 가지의 우선순위 큐 유형:
  • 최대 우선순위 큐(Max-Priority Queue): 우선순위 값이 높은 요소가 먼저 제거됩니다.
  • 최소 우선순위 큐(Min-Priority Queue): 우선순위 값이 낮은 요소가 먼저 제거됩니다.

2. 우선순위 큐의 연산

우선순위 큐는 다음과 같은 주요 연산을 제공합니다:

1. 삽입(Insert):
   • 새로운 요소를 우선순위 큐에 추가합니다.
   • 삽입 연산은 요소의 우선순위를 기준으로 적절한 위치에 배치되도록 해야 합니다.
2. 최대값/최소값 조회(Maximum/Minimum):
   • 현재 큐에서 가장 높은 우선순위를 가진 요소(최대 우선순위 큐의 경우) 또는 가장 낮은 우선순위를 가진 요소(최소 우선순위 큐의 경우)를 반환합니다. 큐에서 해당 요소를 제거하지는 않습니다.
3. 최대값/최소값 제거(Extract-Max/Extract-Min):
   • 가장 높은 우선순위를 가진 요소를 큐에서 제거하고 반환합니다.
   • 이 연산은 우선순위 큐의 핵심 연산 중 하나입니다.
4. 우선순위 증가/감소(Increase/Decrease Priority):
   • 큐에 있는 특정 요소의 우선순위를 변경합니다.
   • 요소의 우선순위를 변경한 후, 큐의 정렬 상태를 유지하도록 재구성해야 합니다.

3. 우선순위 큐의 구현 방법

우선순위 큐는 다양한 방법으로 구현할 수 있으며, 각 방법의 시간 복잡도가 다릅니다:

1. 정렬되지 않은 배열/리스트:
   • 삽입 연산: O(1)O(1)O(1) – 단순히 배열의 끝에 요소를 추가하면 됩니다.
   • 최대값/최소값 제거 연산: O(n)O(n)O(n) – 전체 배열을 순회하여 최대값/최소값을 찾아야 합니다.
2. 정렬된 배열/리스트:
   • 삽입 연산: O(n)O(n)O(n) – 요소를 삽입할 때 올바른 위치를 찾기 위해 정렬된 상태를 유지해야 합니다.
   • 최대값/최소값 제거 연산: O(1)O(1)O(1) – 정렬된 배열에서 첫 번째 또는 마지막 요소를 제거하면 됩니다.
3. 힙(Heap)을 사용한 구현:
   • 일반적으로 우선순위 큐는 **이진 힙(Binary Heap)**을 사용하여 구현합니다. 이진 힙은 완전 이진 트리의 일종으로, 다음 두 가지 특성을 가집니다:
     • 힙 속성: 최대 힙의 경우, 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다. 최소 힙의 경우, 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
     • 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 요소가 채워져 있습니다.
   • 삽입 연산: O(log⁡n)O(\log n)O(logn) – 새로운 요소를 추가한 후 힙 속성을 유지하기 위해 재구성해야 합니다.
   • 최대값/최소값 제거 연산: O(log⁡n)O(\log n)O(logn) – 루트 노드를 제거한 후 힙을 재구성해야 합니다.
   • 힙을 사용한 우선순위 큐는 시간 복잡도 측면에서 매우 효율적입니다.

4. 우선순위 큐의 응용 예시

우선순위 큐는 다양한 알고리즘과 애플리케이션에서 사용됩니다:

1. 다익스트라(Dijkstra) 알고리즘:
   • 그래프에서 최단 경로를 찾는 다익스트라 알고리즘에서는 우선순위 큐를 사용하여 최소 거리를 가진 정점을 선택합니다.
2. 허프만 코딩(Huffman Coding):
   • 데이터 압축 알고리즘인 허프만 코딩에서는 최소 우선순위 큐를 사용하여 최소 빈도 노드들을 합치면서 트리를 만듭니다.
3. 이벤트 시뮬레이션(Event Simulation):
   • 이벤트 기반 시뮬레이션에서는 이벤트의 발생 시간에 따라 우선순위를 부여하여 이벤트를 처리하는 데 사용됩니다.
4. 운영체제의 작업 스케줄링:
   • 우선순위가 높은 프로세스를 먼저 실행하는 작업 스케줄링에서 우선순위 큐가 사용됩니다.

5. 우선순위 큐와 힙의 관계

우선순위 큐는 힙 자료 구조를 통해 구현되는 경우가 많습니다. 힙을 사용하면 우선순위 큐의 삽입과 삭제 연산의 시간 복잡도를 O(log⁡n)O(\log n)O(logn)으로 유지할 수 있습니다.

• 최대 힙(Max-Heap): 최대 우선순위 큐를 구현할 때 사용합니다. 힙의 루트 노드에 가장 큰 값이 위치합니다.
• 최소 힙(Min-Heap): 최소 우선순위 큐를 구현할 때 사용합니다. 힙의 루트 노드에 가장 작은 값이 위치합니다.

---

요약

• 우선순위 큐는 우선순위에 따라 요소를 삽입하고 제거하는 자료 구조입니다. 가장 높은 우선순위(또는 가장 낮은 우선순위)를 가진 요소가 먼저 처리됩니다.
• 다양한 알고리즘(예: 다익스트라 알고리즘, 허프만 코딩)과 시스템(예: 작업 스케줄링)에서 활용됩니다.
• 힙 자료 구조를 사용하여 구현하는 것이 일반적이며, 이를 통해 효율적인 연산을 보장할 수 있습니다.