1. Queue와 Priority Queue의 개념 비교
데이터 처리 순서와 논리적 구조의 근본적인 차이점.
- Queue (큐): 시간 순서상 먼저 삽입된 데이터가 먼저 나오는 선입선출(FIFO, First In First Out) 방식의 자료구조.
- Priority Queue (우선순위 큐): 데이터의 삽입 순서와 관계없이, 사전에 설정된 우선순위가 높은 데이터가 먼저 배출되는 자료구조.
2. 연산별 시간 복잡도 (Time Complexity) 비교
구조적 차이에 따른 연산 효율성의 대조적 결과임.
| 자료구조 | 연산 종류 | 시간 복잡도 | 비고 |
|---|---|---|---|
| Queue | Enqueue / Dequeue | O(1) | 양 끝단에서 즉시 데이터 처리 가능. |
| Priority Queue | Push / Pop | O(log n) | 힙(Heap) 구조를 통한 재정렬 과정 수반. |
3. 우선순위 큐의 구현: Heap (힙)
우선순위 큐를 가장 효율적으로 구현하기 위해 사용되는 완전 이진 트리 기반의 자료구조.
- 힙의 종류:
- Min Heap (최소 힙): 부모 노드의 값이 자식 노드보다 작거나 같으며, Root에 최솟값이 위치함.
- Max Heap (최대 힙): 부모 노드의 값이 자식 노드보다 크거나 같으며, Root에 최댓값이 위치함.
- 배열 기반 구현의 특징:
- 새로운 노드를 마지막 위치에 추가하기 수월하도록 배열(Array)을 기반으로 구현.
- 구현 편의상 인덱스 0번은 사용하지 않음.
- 인덱스 정의: n번째 노드의 왼쪽 자식(2n), 오른쪽 자식(2n+1), 부모 노드(n/2).
4. 힙 연산 및 시간 복잡도 상세 분석
트리의 높이가 log N이라는 점을 이용한 성능 최적화 결과.
- Heap Push (O(log n)): 힙의 마지막 위치에 노드를 추가한 후, 부모 노드와 값을 비교하며 위치를 바꾸는(Swap) 과정을 최대 트리 높이만큼 반복.
- Heap Pop (O(log n)): Root 노드를 추출한 후, 마지막 노드를 Root로 옮겨 자식 노드들과 비교하며 아래로 Swap 하는 재정렬 과정을 최대 트리 높이만큼 수행.
핵심 정리
- 동작 원리: Queue는 들어온 순서(Time)를 따르지만, Priority Queue는 값의 중요도(Priority)를 우선.
- 구현 방식: 효율적인 우선순위 유지를 위해 완전 이진 트리 구조인 Heap을 사용하며, 이는 배열로 구현하여 인덱스 연산으로 관리.
- 면접 포인트: 힙의 시간 복잡도가 왜 O(log n)인지(트리의 높이와 관련), 그리고 배열 구현 시 부모-자식 노드 간의 인덱스 관계를 명확히 설명하는 것이 중요.
추가 정리
Q. 왜 우선순위 큐를 배열로 구현하는 것이 유리한가?
- 완전 이진 트리의 특성상 노드의 추가와 삭제가 ‘마지막 위치’에서 빈번하게 발생하기 때문에, 인덱스만으로 마지막 원소에 즉각 접근하고 부모 노드를 찾을 수 있는 배열이 효율적이기 때문.
Q. 우선순위 큐의 대표적인 활용 사례는?
- 네트워크 데이터 패킷의 우선순위 제어, 다익스트라(Dijkstra) 최단 경로 알고리즘, 운영체제의 CPU 스케줄링 등에서 필수적으로 사용.