우선순위 큐(Priority Queue) 란?

각 요소가 우선순위를 가지고 있는 자료 구조로, 일반적인 큐와 달리 우선순위가 높은 요소가 먼저 처리됨.
우선순위 큐는 힙(Heap) 자료구조로 구현되는 경우가 많으며, 이진 힙(Binary Heap) 을 많이 사용함.

우선순위 큐의 개념

1. 우선순위 큐는 큐와 유사한 자료 구조지만, 각 요소는 우선순위를 가지고 있음.
2. 기본연산
   -삽입(insert) : 새로운 요소를 큐에 삽입
   -삭제(delete) : 우선순위가 가장 높은 요소를 큐에서 제거
   -최대값 / 최소값 반환 : 우선순위가 가장 높은 요소를 삭제하지 않고 반환

우선순위 큐의 시간 복잡도

1. 배열(Array)
   -삽입 : O(1)
   -삭제 : O(n) (최대값 또는 최소값을 찾기 위해 배열 전체를 순회해야 함)

2. 연결 리스트(Linked List)
   -삽입 : O(n) (정렬된 위치에 삽입하기 위해)
   -삭제 : O(1) (정렬된 리스트의 맨 앞 요소를 제거)

3. 힙(Heap)
   -이진 힙(Binary Heap) : 완전 이진 트리로, 최소 힙(min - heap) 과 최대 힙(max - heap) 으로 구분됨
   o 최소 힙(min - heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리. 루트 노드가 가장 작은 값을 가짐
   o 최대 힙(max - heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리. 루트 노드가 가장 큰 값을 가짐
   -삽입 : O(log n)
   -삭제 : O(log n)
   -힙을 사용한 우선순위 큐는 효율적인 삽입과 삭제 연산을 제공

이진 힙을 이용한 우선순위 큐

이진 힙은 배열로 구현될 수 있음. 인덱스 계산을 통해 부모와 자식 노드 간의 관계를 유지 할 수 있음
-부모 노드 인덱스 : (i - 1) // 2
-왼쪽 자식 노드 인덱스 : 2 i + 1
-오른쪽 자식 노드 인덱스 : 2 i + 2

우선순위 큐의 응용

1. 작업 스케쥴링 : 작업을 우선순위에 따라 처리하는데 사용됨
2. 다익스트라 알고리즘 : 최단 경로 탐색 알고리즘에서 우선순위 큐를 사용하여 최단 거리를 가진 정점을 효율적으로 선택
3. 허프만 코딩 : 데이터 압축 알고리즘에서 빈도에 따라 우선순위를 정하고 트리를 구성하는데 사용