우선순위 큐와 힙 (Priority Queue & Heap) 정리
우선순위 큐와 힙 (Priority Queue & Heap)
1. 우선순위 큐가 필요한 이유
일반 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조이고, 스택(Stack)은 마지막에 들어온 데이터가 먼저 나가는 LIFO 구조이다.
하지만 실제 프로그램에서는 입력 순서가 아니라 데이터의 중요도나 우선순위에 따라 처리해야 하는 상황이 있다.
활용 사례
- 작업 스케줄러: 우선순위가 높은 작업을 먼저 처리한다.
- 네트워크 라우팅: 조건에 따라 우선순위가 높은 경로를 먼저 선택한다.
- 길찾기: 현재까지의 비용이 가장 적은 경로를 먼저 확인한다. (Dijkstra, A*)
이러한 상황에서 사용하는 자료구조가 우선순위 큐(Priority Queue)이다.
2. 우선순위 큐의 구현 방식
우선순위 큐는 여러 방법으로 구현할 수 있다.
| 구현 방식 | Enqueue | Dequeue (최솟값) |
|---|---|---|
| 정렬되지 않은 배열 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 힙(Heap) | O(log n) | O(log n) |
정렬되지 않은 배열은 데이터를 추가하기 쉽지만 최솟값을 찾을 때 모든 데이터를 확인해야 한다.
정렬된 배열은 최솟값을 바로 꺼낼 수 있지만 데이터를 추가할 때 정렬 상태를 유지해야 한다.
힙은 삽입과 삭제를 모두 O(log n)에 처리할 수 있어 두 연산이 자주 발생하는 상황에 적합하다.
3. 힙 (Heap)
힙은 완전 이진 트리이면서 부모와 자식 사이에 특정한 우선순위 규칙을 유지하는 자료구조이다.
Min-Heap
부모 노드의 값이 자식 노드의 값보다 작거나 같아야 한다.
- 루트에는 항상 최솟값이 위치한다.
- 자식 노드끼리의 크기 순서는 정해져 있지 않다.
Max-Heap
부모 노드의 값이 자식 노드의 값보다 크거나 같아야 한다.
- 루트에는 항상 최댓값이 위치한다.
- 자식 노드끼리의 크기 순서는 정해져 있지 않다.
이 프로젝트에서는 길찾기 과정에서 비용이 가장 작은 노드를 먼저 처리하기 위해 Min-Heap을 구현한다.
4. 완전 이진 트리 (Complete Binary Tree)
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨은 왼쪽부터 순서대로 채워진 이진 트리이다.
완전 이진 트리는 배열로 효율적으로 표현할 수 있다는 특징이 있다.
배열 표현
힙은 노드 간의 연결을 별도의 참조로 저장하지 않고 배열의 인덱스를 이용하여 표현할 수 있다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 값 | 1 | 3 | 5 | 7 | 4 | 8 |
인덱스 계산 규칙
배열 인덱스가 i인 노드를 기준으로 다음과 같이 부모와 자식의 위치를 계산한다.
| 관계 | 계산식 |
|---|---|
| 부모 | (i - 1) / 2 |
| 왼쪽 자식 | 2 * i + 1 |
| 오른쪽 자식 | 2 * i + 2 |
정수 나눗셈을 사용하므로 부모 인덱스는 소수점 이하가 버려진다.
배열로 표현하는 장점
- 별도의 노드 연결 참조가 필요하지 않다.
- 인덱스 계산만으로 부모와 자식에 접근할 수 있다.
- 메모리를 효율적으로 사용할 수 있다.
- 배열에 데이터가 연속적으로 저장되어 캐시 지역성이 좋다.
5. Min-Heap의 핵심 연산
Min-Heap은 부모 노드가 자식 노드보다 작거나 같은 상태를 유지해야 한다.
따라서 데이터를 삽입하거나 삭제할 때 힙의 규칙을 다시 맞추는 과정이 필요하다.
Enqueue (Insert) - HeapifyUp
새로운 데이터를 힙에 추가하는 연산이다.
처리 순서
- 새로운 원소를 배열의 마지막 위치에 추가한다.
- 추가된 원소와 부모 노드의 우선순위를 비교한다.
- 새로운 원소가 부모보다 작으면 두 노드를 교환한다.
- 부모 노드의 위치로 이동하여 다시 비교한다.
- 부모보다 크거나 같거나 루트에 도달하면 종료한다.
이처럼 아래에서 위로 올라가며 힙의 규칙을 복구하는 과정을 HeapifyUp이라고 한다.
시간 복잡도: O(log n)
완전 이진 트리의 높이만큼만 이동하기 때문이다.
Dequeue (ExtractMin) - HeapifyDown
Min-Heap에서 최솟값을 제거하고 반환하는 연산이다.
최솟값은 항상 루트에 있으므로 배열의 첫 번째 원소를 제거 대상으로 선택한다.
처리 순서
- 루트에 있는 최솟값을 결과로 보관한다.
- 배열의 마지막 원소를 루트 위치로 이동한다.
- 왼쪽과 오른쪽 자식 중 더 작은 값을 찾는다.
- 현재 노드가 더 작은 자식보다 크면 두 노드를 교환한다.
- 교환한 위치에서 다시 자식 노드와 비교한다.
- 자식이 없거나 현재 노드가 더 작은 자식보다 작거나 같으면 종료한다.
이처럼 위에서 아래로 내려가며 힙의 규칙을 복구하는 과정을 HeapifyDown이라고 한다.
시간 복잡도: O(log n)
완전 이진 트리의 높이만큼만 이동하기 때문이다.
Peek
힙에서 최솟값을 제거하지 않고 확인하는 연산이다.
Min-Heap의 최솟값은 항상 루트에 있으므로 배열의 첫 번째 원소를 반환하면 된다.
시간 복잡도: O(1)
6. 힙의 시간 복잡도
완전 이진 트리의 높이는 노드 수를 기준으로 O(log n)이다.
HeapifyUp과 HeapifyDown은 한 번에 한 레벨씩 이동하므로 최악의 경우에도 트리의 높이만큼만 비교하고 교환한다.
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| Enqueue | O(log n) | 원소 추가 및 위로 이동 |
| Dequeue | O(log n) | 최솟값 제거 및 아래로 이동 |
| Peek | O(1) | 루트 원소 확인 |
| Count | O(1) | 저장된 원소 개수 확인 |
| Clear | O(n) | 내부 저장소 비우기 |
힙은 삽입과 삭제가 반복되는 상황에서도 두 연산을 균형 있게 처리할 수 있다는 장점이 있다.
7. 프로젝트의 우선순위 큐 구현
프로젝트에서는 PriorityQueue<TElement, TPriority> 형태로 우선순위 큐를 구현한다.
주요 구성
TElement: 실제로 저장하고 반환할 데이터의 타입이다.TPriority: 데이터의 우선순위를 나타내는 타입이다.Count: 현재 저장된 원소의 개수이다.Enqueue(): 원소와 우선순위를 함께 추가한다.Dequeue(): 우선순위가 가장 높은 원소를 제거하고 반환한다.Peek(): 우선순위가 가장 높은 원소를 제거하지 않고 확인한다.Clear(): 내부 데이터를 모두 제거한다.
두 가지 제네릭 타입을 사용하는 이유
실제 데이터와 우선순위를 분리하기 위해 사용한다.
예를 들어 길찾기에서는 GraphNode 객체를 저장하면서 해당 노드까지 이동하는 비용을 int로 관리할 수 있다.
이렇게 분리하면 실제 데이터가 직접 비교 가능한 타입일 필요가 없다.
Comparer.Default
Comparer<TPriority>.Default는 우선순위를 비교할 때 사용하는 기본 비교자이다.
int, float, string처럼 기본 비교가 가능한 타입은 기본 비교 규칙을 사용할 수 있다.
오름차순 비교를 사용하면 작은 우선순위 값이 먼저 나오므로 Min-Heap으로 동작한다.
내부 저장소
내부 저장소는 다음과 같은 형태로 구성한다.
List<(TElement Element, TPriority Priority)>
튜플을 사용하여 실제 원소와 우선순위를 하나로 묶어 저장한다.
Element: 실제 데이터이다.Priority: 우선순위를 나타내는 값이다.
Dequeue는 실제 원소인 Element만 반환한다. Priority는 힙 내부에서 원소의 순서를 결정하는 데 사용한다.
8. 길찾기에서의 활용
우선순위 큐는 Dijkstra와 A* 같은 길찾기 알고리즘에서 활용된다.
길찾기 과정에서는 여러 노드 중 현재까지의 이동 비용이 가장 작은 노드를 먼저 처리해야 한다.
우선순위 큐를 사용하면 매번 모든 노드를 검색하지 않고 가장 작은 우선순위의 노드를 효율적으로 가져올 수 있다.
동작 구조
- 시작 노드를 우선순위 0으로 추가한다.
- 우선순위 큐에서 가장 비용이 낮은 노드를 꺼낸다.
- 해당 노드와 연결된 주변 노드를 확인한다.
- 이동 비용을 계산하고 필요한 노드를 큐에 추가하거나 갱신한다.
- 큐가 빌 때까지 반복한다.
이러한 방식으로 우선순위가 높은 노드부터 차례대로 탐색한다.
9. 전체 구조 정리
우선순위 큐는 데이터의 입력 순서가 아닌 우선순위에 따라 원소를 꺼내는 자료구조이다.
- Priority Queue: 우선순위에 따라 데이터를 관리한다.
- Heap: 우선순위 큐를 효율적으로 구현하는 자료구조이다.
- Complete Binary Tree: 힙의 배열 표현을 가능하게 한다.
- Min-Heap: 가장 작은 값을 루트에 유지한다.
- HeapifyUp: 새로운 원소를 추가한 뒤 위쪽으로 이동하며 균형을 복구한다.
- HeapifyDown: 최솟값을 제거한 뒤 아래쪽으로 이동하며 균형을 복구한다.
- Comparer: 우선순위를 비교하는 기준을 제공한다.
핵심은 완전 이진 트리를 배열로 표현하고, 삽입과 삭제 시 Heapify 과정을 통해 우선순위 규칙을 유지하는 것이다.



