우선순위 큐 (Priority Queue)

우선순위 큐 (Priority Queue)

각 요소가 우선순위를 가지며 우선순위가 높은 요소가 먼저 제거되는 추상 자료형으로, 일반적으로 힙(Heap)으로 구현되어 삽입·삭제가 O(log n)에 수행

목적: 우선순위 기반 처리, 동적 정렬, 최대/최소값 추출, 작업 스케줄링

특징: 우선순위 순서, 동적 정렬, FIFO 아님, 힙 기반 구현

연산

• •insert(item, priority): 삽입, O(log n)
• •extractMax()/extractMin(): 최대/최소 제거 및 반환, O(log n)
• •peek(): 최대/최소 조회(제거 없음), O(1)
• •changePriority(): 우선순위 변경, O(log n)

구현: 힙(이진 힙, 피보나치 힙), 정렬 배열, 이진 탐색 트리

시간 복잡도

• •삽입: O(log n) - 힙
• •최대/최소 제거: O(log n) - 힙
• •최대/최소 조회: O(1) - 힙

공간 복잡도: O(n)

장점: 효율적 최대/최소 추출, 동적 우선순위, 다양한 응용

단점: 임의 접근 불가, 일반 탐색 비효율(O(n)), 구현 복잡도

적용사례

• •다익스트라 최단 경로
• •A* 알고리즘
• •허프만 코딩
• •이벤트 시뮬레이션
• •CPU 스케줄링
• •Heap Sort
• •Prim MST

비교: 우선순위큐(우선순위/O(log n)) vs 일반큐(FIFO/O(1))

연관: 힙, 이진 힙, 다익스트라, Heap Sort