PriorityQueue (우선순위 큐)

PriorityQueue는 우선순위 큐(priority queue)를 구현한 자료구조입니다.

이는 우선순위(priority)를 가진 항목들을 저장하는 큐로, 항목의 우선순위에 따라 항목들이 저장/제거됩니다. 

PriorityQueue는 내부적으로 배열이나 힙(heap)등의 자료구조를 사용하여 구현될 수 있습니다.

대표적으로는 최소 힙(min heap)을 기반으로 구현되어,
저장된 항목 중 우선순위가 가장 높은(값이 가장 낮은) 항목이 가장 먼저 제거됩니다.

PriorityQueue의 주요 메서드는 다음과 같습니다:

- add(E e): 큐에 항목 e를 삽입합니다. 
- peek(): 큐의 제일 앞, 즉 우선순위가 가장 높은 항목을 반환합니다. 
- poll(): 큐의 제일 앞 항목을 제거하고 반환합니다.
- size(): 큐에 들어있는 항목의 개수를 반환합니다.

import java.util.PriorityQueue;

public class PriorityQueueExample {
  public static void main(String[] args) {

    PriorityQueue<Integer> pq = new PriorityQueue<>();

    // 우선순위 큐에 값 삽입
    pq.offer(30); 
    pq.offer(20);
    pq.offer(10);

    // 우선순위 큐의 값 확인
    System.out.println(pq); // [10, 20, 30]

    // 우선순위가 가장 높은 값 반환 및 제거
    System.out.println(pq.poll()); // 10 

    // 우선순위 큐의 값 확인
    System.out.println(pq); // [20, 30]

  }
}

PriorityQueue는 기본적으로 최소 힙을 기반으로 구현되어 있습니다. 

따라서 숫자 값을 기준으로 하였을 때, 가장 작은 값인 10이 가장 먼저 반환되었습니다.

poll() 메서드를 통해 우선순위 큐의 항목을 하나씩 제거할 수 있습니다.

힙(Heap)은 자료구조의 한 종류로, 최대값/최소값을 빠르게 찾기 위해 고안된 완전 이진 트리를 기본으로 하는 자료구조입니다.

주요 특징은 다음과 같습니다:
- 최대 힙(max heap)은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- 최소 힙(min heap)은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- 루트 노드가 가장 큰/작은 값을 가짐
- 힙의 삽입, 삭제 연산의 시간 복잡도는 O(logN)
- 우선순위 큐, 정렬 알고리즘(힙 정렬), 다익스트라 알고리즘 등에서 응용됨

힙은 배열이나 포인터를 이용해 저장하며, 부모/자식 노드의 관계를 이용한 효율적인 정렬이 가능한 자료구조입니다.

 

PriorityQueue는 우선순위가 필요한 다양한 알고리즘 구현에 사용될 수 있습니다.

예를 들어 다익스트라 최단 경로 알고리즘, A* 탐색 알고리즘 등에서 활용할 수 있습니다.

다익스트라(Dijkstra) 알고리즘은 주어진 그래프의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.

알고리즘 순서는 다음과 같습니다:
- 출발 정점을 설정합니다.
- 출발 정점을 기준으로 각 정점까지의 최단 거리를 저장합니다.
- 방문하지 않은 정점 중 출발 정점과의 최단 거리가 가장 짧은 정점을 선택합니다.
- 해당 정점을 거쳐 가는 경우를 고려하여 각 정점의 최단 거리를 업데이트합니다.
- 3~4번 과정을 반복하여 모든 정점을 방문할 때까지 수행합니다.

우선순위 큐(Priority Queue)를 사용하여 시간 복잡도를 O(E+VlogV)로 개선할 수 있습니다.
최단 거리가 가장 짧은 정점을 찾기 위해 우선순위 큐를 사용합니다.
다익스트라 알고리즘은 GPS 네비게이션과 같이 최단 경로를 찾아야 하는 경우에 많이 사용됩니다.

A* 탐색 알고리즘(A* Search Algorithm)은 그래프에서 출발 노드에서 목표 노드까지의 최적 경로를 찾는 알고리즘입니다.

A* 알고리즘은 다음 두 가지 정보를 사용합니다.
- g(n) : 출발 노드에서 현재 노드 n까지의 경로 비용
- h(n) : 현재 노드 n에서 목표 노드까지의 예상 경로 비용

현재 노드에서 인접 노드로의 이동 순서는 f(n)을 기준으로 결정합니다.
f(n) = g(n) + h(n)
즉, 실제 비용과 예상 비용의 합이 가장 작은 노드가 선택됩니다.

h(n)를 휴리스틱(heuristic) 함수라고 하는데, 이 함수가 최적의 결과를 보장합니다.
일반적으로 직선 거리를 휴리스틱 함수로 사용합니다.

A* 알고리즘은 게임 AI에서 캐릭터의 경로 탐색에 주로 사용되는 알고리즘입니다.
탐색 속도가 빠르고 최적의 경로를 찾을 수 있는 장점이 있습니다.

 

PriorityQueue는 많은 프로그래밍 언어와 알고리즘 라이브러리에서 구현되어 있는 자료구조입니다.

- C++에는 priority_queue라는 이름으로 STD 라이브러리에 구현되어 있습니다.

- 파이썬에는 heapq 모듈을 통해 유사한 기능의 자료구조를 제공합니다.

- 자바스크립트에서도 기본 자료구조 없이 PriorityQueue를 직접 구현할 수 있습니다.

- Rust, Go 언어 등 다양한 언어에서도 PriorityQueue 자료구조를 사용할 수 있습니다.

- 알고리즘 라이브러리인 Boost, MATLAB, NumPy 등에서도 PriorityQueue를 지원합니다.

PriorityQueue는 다양한 프로그래밍 언어와 환경에서 범용적으로 사용할 수 있는 핵심적인 자료구조입니다. 

특히 우선순위가 필요한 알고리즘을 구현할 때 유용하게 사용됩니다.