PriorityQueue(우선순위 큐)는 단순히 먼저 들어온 순서대로 데이터를 꺼내는 구조가 아니라, 우선순위가 높은 데이터부터 꺼내는 자료구조입니다. 일반적인 Queue가 FIFO(First-In First-Out) 구조라면, PriorityQueue는 “가장 중요한 것부터 처리한다”는 관점에서 동작합니다.
이번 문서에서 구현하는 PriorityQueue는 Min-Heap(최소 힙) 기반 구조입니다. 즉, “값이 작은 데이터일수록 우선순위가 높다”라고 가정하며, 내부적으로는 배열 기반의 최소 힙(Min-Heap)을 사용하여 항상 가장 작은 값을 빠르게 꺼낼 수 있도록 구성합니다.
여기서 중요한 점은, 힙은 전체 데이터가 정렬된 형태를 유지하는 자료구조가 아니라는 것입니다. 외부에서 정확한 순서가 보장되는 위치는 사실상 루트(배열의 0번 인덱스) 하나뿐이며, 이 루트 값이 항상 가장 작은 값이 되도록 보장됩니다. 루트 아래에 있는 데이터들은 전체적으로 정렬되어 있지는 않지만, 각 노드에 대해 “부모 ≤ 자식”이라는 힙 조건만 만족하면 힙 구조로서 완전합니다.
- 힙은 완전 이진 트리 형태의 논리적 구조를 가지며, 이를 보통 1차원 배열로 구현하여 부모–자식 관계를 인덱스로 계산할 수 있는 자료구조입니다.
- 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨에서는 노드가 왼쪽부터 순서대로 채워진 트리를 말합니다.
- 트리에 대한 좀 더 자세한 내용은 Unity 개발자를 위한 C# Tree(트리) 구현을 참고하세요.
1. PriorityQueue의 구조와 동작 방식
PriorityQueue는 전체 데이터를 정렬해 두는 구조가 아니라, “가장 우선순위가 높은 값만 항상 빠르게 꺼낼 수 있도록 유지되는” 자료구조입니다.
이번 구현에서는 값이 작을수록 더 중요하다(Min-Heap)라고 정해놓습니다.
1.1 PriorityQueue는 어떻게 생겼나?
겉모습은 “이진 트리”처럼 생겼지만, 실제 내부 구조는 동적 배열 하나(List<T>)로 구성됩니다.
왜 배열 하나로 트리를 표현할 수 있을까요? 트리는 보통 다음과 같은 구조를 갖지만,
(부모)
/ \
(왼쪽) (오른쪽)
이 구조를 배열의 인덱스 규칙으로 계산할 수 있기 때문입니다.
1.2 배열에서의 부모·자식 관계
배열에서 어떤 값의 위치가 index일 때:
- 부모 위치 =
(index - 1) / 2 - 왼쪽 자식 =
index * 2 + 1 - 오른쪽 자식 =
index * 2 + 2
* index가 int이기 때문에 연산 시 소수점은 버려집니다.
1.2.1 트리 그림과 배열 그림으로 이해하는 Heap 구조
예를 들어 다음과 같은 이진트리를 배열로 표현해 보겠습니다.
(0)
/ \
(1) (2)
/ \ / \
(3) (4) (5) (6)
괄호 안의 숫자는 “배열 인덱스”라고 가정한 것입니다.
1) 트리 모습
A(0)
/ \
B(1) C(2)
/ \ / \
D(3) E(4) F(5) G(6)
2) 배열 모습
트리를 배열에 나열하면 이렇게 됩니다:
Index: 0 1 2 3 4 5 6
Value: A B C D E F G
1.2.2 실제로 대입해보면?
예: 인덱스 1(B)의 부모 찾기
부모 = (1 - 1) / 2 = 0 → A
즉 B의 부모는 A (트리에서 맞음)
예: 인덱스 3(D)의 부모 찾기
부모 = (3 - 1) / 2 = 1 → B
D의 부모는 B — 트리에서 동일함.
예: 인덱스 1(B)의 왼쪽 자식
왼쪽 자식 = 1 * 2 + 1 = 3 → D
예: 인덱스 1(B)의 오른쪽 자식
오른쪽 자식 = 1 * 2 + 2 = 4 → E
트리와 정확히 일치합니다.
1.2.3 이렇게 연결 리스트 없이도 트리를 만들 수 있는 이유
이진 힙(Binary Heap)은 완전 이진트리 구조이기 때문에 노드들이 “왼쪽부터 차곡차곡” 채워져 있습니다.
즉:
- 빈 공간이 없고
- 왼쪽 → 오른쪽, 위 → 아래 순서로 채워짐
이 규칙 덕분에 트리를 노드 연결(linked) 방식으로 만들지 않고도 배열만으로 모든 부모/자식 관계를 정확하게 표현할 수 있습니다.
1.3 Min-Heap은 어떤 규칙을 가지고 있을까?
Min-Heap의 규칙은 단 하나입니다.
부모의 값 ≤ 자식의 값
즉, “부모는 항상 자식보다 작거나 같아야 한다”는 뜻입니다. 그래서 트리의 맨 위(루트)에는 항상 가장 작은 값이 오게 됩니다. PriorityQueue가 “가장 중요한 값”을 빠르게 꺼낼 수 있는 이유가 바로 이 규칙입니다.
1.4 삽입(Enqueue)이 일어날 때
삽입 순서는 중요하지 않습니다. (1, 2, 3 순으로 넣든 2, 3,1 순으로 넣든 상관 없음)
새로운 값을 배열의 맨 뒤에 넣고, 그 값을 부모와 비교하며 위로 올라가게(HeapifyUp) 합니다.
- 새 값이 부모보다 작으면 → 자리 바꿈
- 부모보다 크면 → 멈춤
이 과정을 반복하면 어느 위치에 넣든 힙 규칙이 자동으로 맞춰집니다.
1.4.1 트리 예시
다음 예시는 새로운 값을 배열의 맨 뒤에 넣고, 부모와 비교하며 위로 올라가는(HeapifyUp) 과정을 트리 그림으로 보여줍니다.
✔ 초기 힙 상태 (삽입 전)
초기에 힙이 다음과 같은 상태라고 가정합니다.
배열 상태
0 1 2 3 4
[1 3 4 8 6]
1
/ \
3 4
/ \
8 6
Step 1 - 새 값을 “배열 맨 뒤”에 추가
배열 상태
0 1 2 3 4 5
[1 3 4 8 6 (2)] <- 2 추가됨
1
/ \
3 4
/ \ /
8 6 (2) ← 새로 추가된 노드 (index 5)- 이때, 새 노드 2의 인덱스는 5이며, 부모 인덱스는 (5 - 1) / 2 = 2입니다. 부모 노드의 값은 4입니다.
Step 2 - 부모와 비교 후 교환 (1차 HeapifyUp)
현재 노드 값 = 2 (index 5)
부모 노드 값 = 4 (index 2)
부모(4) > 자식(2) 이므로 두 노드를 교환합니다. (부모 <= 자식 이어야 함)
배열 상태
0 1 2 3 4 5
[1 3 (2) 8 6 (4)] <- 4, 2가 바뀜
1
/ \
3 (2)
/ \ /
8 6 (4)- 이제 HeapifyUp 대상 노드의 인덱스는 부모 인덱스였던 2가 됩니다. 새 위치에서 다시 부모와 비교를 진행합니다.
Step 3 - 다시 부모와 비교 후 종료 (2차 HeapifyUp)
현재 노드 값 = 2 (index 2)
부모 노드 값 = 1 (index 0)
부모(1) <= 자식(2) 이므로 더 이상 위로 올라갈 필요가 없고, HeapifyUp을 종료합니다.
최종 힙 상태 (삽입 후)
0 1 2 3 4 5
[1 3 2 8 6 4]
1
/ \
3 2
/ \ /
8 6 4- 최종적으로 Min-Heap 규칙(부모 ≤ 자식)을 만족하는 힙이 되었으며, 새로 삽입한 값 2는 적절한 위치(index 2)로 이동했습니다.
정리
- 새 값은 항상 배열의 맨 뒤에 추가된다.
- 부모보다 값이 작으면 부모와 자리 바꿈을 하며 위로 올라간다.
- 부모보다 크거나 같아지는 순간 멈추고, 이 과정을 통해 Min-Heap 규칙이 자동으로 유지된다.
1.5 삭제(Dequeue)가 일어날 때
삭제(Dequeue)는 현재 우선순위가 가장 높은 값, 즉 루트 노드(배열 0번 인덱스)를 꺼내는 과정입니다. Min-Heap 기준으로는 가장 작은 값을 제거하는 연산입니다.
삭제 과정은 다음과 같은 순서로 진행됩니다.
- 루트 값을 꺼낸다.
- 배열의 맨 마지막 값을 루트 위치(0번 인덱스)로 가져온다.
- 루트에서 시작해서 자식 노드와 비교하며 아래로 내려간다(HeapifyDown).
- 더 이상 내려갈 필요가 없을 때까지 반복한다.
1.5.1 트리 예시
아래 예시는 루트 값을 삭제할 때 어떤 식으로 트리와 배열이 변하는지 단계별로 보여줍니다. 삽입 예시에서 최종적으로 만들어진 힙에서 Dequeue()를 호출한다고 가정합니다.
초기 힙 상태 (삭제 전)
배열 상태
0 1 2 3 4 5
[1 3 2 8 6 4]
1
/ \
3 2
/ \ /
8 6 4
이 상태에서 Dequeue()를 호출하면, 먼저 루트 값인 1을 결과로 반환해야 합니다. 그리고 힙 구조를 유지하기 위해 아래와 같은 과정을 수행합니다.
Step 1 - 루트 제거 및 마지막 노드를 루트로 이동
- 루트 값 1을 임시로 저장합니다. (Dequeue의 반환값이 됩니다.)
- 배열의 마지막 값 4를 루트 자리(인덱스 0)로 가져옵니다.
- 배열 마지막 원소를 제거하여 길이를 1 줄입니다.
이전:
[1 3 2 8 6 4]
과정:
- 루트(1) 저장
- 마지막 값(4)을 index 0으로 이동
- 마지막 원소 제거
결과:
0 1 2 3 4
[(4) 3 2 8 6] ← 마지막 값이었던 4가 root(0번 인덱스)로 이동
(4) ← 마지막 노드가 루트로 이동
/ \
3 2
/ \
8 6
이제 루트에 있던 값이 4로 바뀌었기 때문에, Min-Heap 규칙(부모 ≤ 자식)을 깨뜨릴 수 있습니다. (위에서는 이미 깨졌음) 따라서 HeapifyDown을 통해 루트에서 아래로 내려가며 다시 힙 구조를 맞춰야 합니다.
Step 2 - 자식과 비교하며 내려가기 (1차 HeapifyDown)
- 자식 중 작은 값과 바꿔야 합니다.
현재 노드: index 0, 값 = 4
왼쪽 자식: index 1, 값 = 3
오른쪽 자식: index 2, 값 = 2- 왼쪽 자식 3, 오른쪽 자식 2 중에서 더 작은 값은 2입니다.
- Min-Heap에서는 부모 ≤ 자식이어야 하므로, 4와 2의 위치를 바꿔야 합니다.
교환 후
이전:
0 1 2 3 4
[4 3 2 8 6]
index 0 (4) ↔ index 2 (2) 교환
결과:
0 1 2 3 4
[(2) 3 (4) 8 6]
(2)
/ \
3 (4)
/ \
8 6
이제 HeapifyDown 대상 노드는 새로 이동한 4가 있는 index 2가 됩니다. 해당 위치에서 다시 자식이 있는지, 규칙을 깨뜨리지 않는지 확인해야 합니다.
Step 3 - 다시 자식과 비교 후 종료 (2차 HeapifyDown)
현재 노드: index 2, 값 = 4
왼쪽 자식 index = 2 * 2 + 1 = 5
오른쪽 자식 index = 2 * 2 + 2 = 6
배열 길이는 5이므로, index 5와 6은 유효한 노드가 아닙니다.
즉, 더 이상 내려갈 자식이 없습니다.- 자식이 없기 때문에 추가 비교/교환은 필요 없으며, HeapifyDown 과정은 여기서 종료됩니다.
최종 힙 상태 (삭제 후)
0 1 2 3 4
[2 3 4 8 6]
2
/ \
3 4
/ \
8 6- 최종적으로 Min-Heap 규칙(부모 ≤ 자식)을 만족하는 힙이 되었으며, 루트였던 값 1은 Dequeue의 반환값으로 사용되고, 새로운 최솟값 2가 루트(배열 0번 인덱스)에 위치하게 됩니다.
정리
- Dequeue는 항상 루트(배열 0번)의 값을 제거하고 반환한다.
- 루트가 사라지면 배열의 마지막 값을 루트 자리로 이동시킨다.
- 이후 루트에서 시작해 자식 노드들과 값을 비교하며 더 작은 자식과 교환하면서 내려간다(HeapifyDown).
- 더 이상 내려갈 자식이 없거나, 부모 ≤ 자식 관계가 만족되면 HeapifyDown을 종료한다.
- 이 과정을 통해 삭제가 일어나도 Min-Heap 규칙이 자동으로 유지된다.
2. PriorityQueue가 활용되는 대표적인 사례
PriorityQueue는 게임 개발을 포함한 다양한 분야에서 자주 사용되는 자료구조입니다. 특히 “모든 작업을 한 번에 처리할 수는 없지만, 더 중요한 작업부터 처리해야 할 때” 유용합니다.
- 경로 탐색 알고리즘 (A* 등)
A* 알고리즘의Open List는 보통 “현재까지 비용 + 휴리스틱” 값이 가장 작은 노드부터 탐색해야 합니다. 이때 노드들을 우선순위 큐에 넣어두고, 매번 최소 비용 노드를 꺼내 탐색하면 효율적으로 구현할 수 있습니다. - 스케줄링 / 타이머 관리
특정 시간에 실행해야 하는 이벤트들을 “실행 시각” 기준으로 정렬해 관리할 때, 가까운 미래에 실행될 이벤트부터 처리해야 합니다. 실행 시각이 가장 빠른 이벤트를 우선순위 큐의 최솟값으로 두고, 매 프레임 또는 주기적으로 확인하여 처리할 수 있습니다. - AI 태스크 처리
AI 캐릭터가 여러 개의 행동 후보를 가지고 있을 때, “위험도가 높은 상황”이나 “긴급한 명령”을 우선 처리해야 할 수 있습니다. 행동의 우선순위를 점수화해 PriorityQueue에 넣고, 점수가 가장 높은(또는 낮은) 행동을 먼저 꺼내 실행하는 식으로 사용할 수 있습니다. - 대미지 처리, 버프/디버프 만료 처리
시간에 따라 만료되는 효과(버프, 디버프, DOT 등)를 “만료 시간” 기준으로 PriorityQueue에 넣고, 가장 먼저 만료되는 효과부터 차례대로 처리하는 구조를 만들 수 있습니다.
이처럼 PriorityQueue는 언제나 가장 중요한 것 하나를 빠르게 꺼내야 할 때 매우 적합한 자료구조입니다.
3. PriorityQueue가 제공하는 기능(구현 기준)
이번에 구현한 PriorityQueue<T>는 다음과 같은 기능을 제공합니다.
- 생성자
PriorityQueue(IComparer<T> cmp = null)
기본 생성자에서IComparer<T>를 인자로 받을 수 있습니다. 전달하지 않으면Comparer<T>.Default를 사용하며, 이 경우T가IComparable<T>또는IComparable을 구현하고 있어야 합니다.- PriorityQueue는 내부적으로 IComparer<T>를 사용해 값의 우선순위를 결정합니다. 그래서 어떤 Comparer를 사용하느냐에 따라 작은 값이 먼저 나오는 Min-Heap이 될 수도 있고, 큰 값이 먼저 나오는 Max-Heap이 될 수도 있습니다.
- Count
현재 힙에 들어 있는 원소 개수를 반환합니다. - Enqueue(T item)
새로운 원소를 우선순위 큐에 추가합니다. 내부적으로는 마지막 인덱스에 삽입한 뒤,HeapifyUp을 통해 힙 속성을 만족하도록 위로 끌어올립니다. 시간 복잡도는 평균/최악 모두 O(log N)입니다. - Dequeue()
현재 우선순위가 가장 높은(값이 가장 작은) 원소를 제거하고 반환합니다. 루트(인덱스 0)를 꺼낸 뒤, 마지막 원소를 루트 위치로 옮기고HeapifyDown을 수행합니다. 시간 복잡도는 평균/최악 모두 O(log N)입니다. - Peek()
현재 우선순위가 가장 높은 원소를 삭제하지 않고 확인합니다. 내부 배열의 인덱스 0을 그대로 반환하므로 시간 복잡도는 O(1)입니다. - Clear()
내부 힙을 비웁니다._heap.Clear()를 호출하여 모든 데이터를 제거합니다.
4. PriorityQueue의 내부 동작 방식
이제 PriorityQueue가 내부적으로 어떻게 동작하는지, 실제 코드 흐름을 기준으로 단계별로 살펴보겠습니다. 이번 구현은 Min-Heap(최소 힙) 기반으로, 항상 가장 작은 값이 루트(배열 0번 인덱스)에 오도록 유지합니다.
4.1 내부 배열 구조
PriorityQueue는 List<T> _heap 하나로 완전 이진트리를 표현합니다. 트리는 개념적인 구조일 뿐이고, 실제 데이터는 모두 1차원 배열에 저장됩니다.
각 노드는 다음과 같은 인덱스 규칙을 따릅니다(0 기반 인덱스).
- 부모 인덱스:
parent = (index - 1) / 2 - 왼쪽 자식 인덱스:
left = index * 2 + 1 - 오른쪽 자식 인덱스:
right = index * 2 + 2
Min-Heap에서는 항상 부모 값 ≤ 자식 값을 만족해야 합니다. 이 규칙이 깨지지 않도록, 삽입 시에는 HeapifyUp, 삭제 시에는 HeapifyDown을 수행합니다.
4.2 Enqueue 흐름 (삽입)
새로운 값을 PriorityQueue에 추가하는 동작은 Enqueue 메서드에서 처리합니다. 기본 흐름은 다음과 같습니다.
- 1) 새 값을 배열의 맨 뒤에 추가한다.
- 2) 부모와 값을 비교하면서 위로 올라가며(HeapifyUp) 위치를 조정한다.
- 3) 부모 값 ≤ 현재 값이 되거나 루트에 도달하면 멈춘다.
실제 코드는 다음과 같습니다.
public void Enqueue(T item)
{
_heap.Add(item); // 1) 배열의 맨 뒤에 추가
HeapifyUp(_heap.Count - 1); // 2) 부모와 비교하며 위로 이동
}
private void HeapifyUp(int index)
{
// 삽입한 노드를 부모와 비교하여 올바른 위치까지 위로 이동
while (index > 0)
{
int parent = (index - 1) / 2;
// 부모보다 크거나 같으면(우선순위가 낮으면) 종료
if (_cmp.Compare(_heap[index], _heap[parent]) >= 0)
{
break;
}
Swap(index, parent); // 부모와 교환
index = parent; // 부모 위치로 갱신
}
}
예를 들어 배열이 [1, 3, 4, 8, 6]인 상태에서 값 2를 Enqueue 하면:
초기 배열
0 1 2 3 4
[1 3 4 8 6]
Enqueue(2) 후
0 1 2 3 4 5
[1 3 4 8 6 (2)] <- index 5에 추가
HeapifyUp 진행:
- index 5 (값 2), parent = 2 (값 4) → 2 < 4 이므로 교환
0 1 2 3 4 5
[1 3 (2) 8 6 (4)]
- index 2 (값 2), parent = 0 (값 1) → 2 ≥ 1 이므로 종료
최종 배열
0 1 2 3 4 5
[1 3 2 8 6 4]
이 과정에서 전체가 정렬되지는 않지만, 배열 0번 인덱스에는 항상 가장 작은 값이 유지됩니다. 삽입 연산의 시간 복잡도는 트리 높이에 비례하는 O(log N)입니다.
4.3 Dequeue 흐름 (삭제)
삭제(Dequeue)는 현재 우선순위가 가장 높은 값, 즉 Min-Heap에서는 가장 작은 값을 꺼내는 작업입니다. 항상 루트(배열 0번 인덱스)에서 값을 꺼냅니다.
- 1) 루트 값을 결과로 저장한다.
- 2) 배열의 마지막 값을 루트 위치로 가져온다.
- 3) 마지막 원소를 제거해 배열 길이를 줄인다.
- 4) 루트에서 시작해 자식과 비교하면서 아래로 내려가며(HeapifyDown) 위치를 조정한다.
실제 코드는 다음과 같습니다.
public T Dequeue()
{
if (_heap.Count == 0)
{
throw new InvalidOperationException("큐가 비어 있습니다.");
}
T root = _heap[0]; // 1) 루트 값 저장
int lastIndex = _heap.Count - 1;
_heap[0] = _heap[lastIndex]; // 2) 마지막 원소를 루트로 이동
_heap.RemoveAt(lastIndex); // 3) 마지막 원소 제거
if (_heap.Count > 0)
{
HeapifyDown(0); // 4) 루트에서 아래로 정리
}
return root;
}
private void HeapifyDown(int index)
{
// 루트에서 시작하여 자식들과 비교하며 내려가는 과정
int lastIndex = _heap.Count - 1;
while (true)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
int smallest = index;
// 왼쪽 자식이 더 작은 경우
if (left <= lastIndex && _cmp.Compare(_heap[left], _heap[smallest]) < 0)
{
smallest = left;
}
// 오른쪽 자식이 더 작은 경우
if (right <= lastIndex && _cmp.Compare(_heap[right], _heap[smallest]) < 0)
{
smallest = right;
}
// 더 이상 내려갈 필요 없음
if (smallest == index)
{
break;
}
Swap(index, smallest); // 더 작은 자식과 교환
index = smallest; // 위치 갱신
}
}
예를 들어 배열이 [1, 3, 2, 8, 6, 4]인 상태에서 Dequeue()를 호출하면:
초기 배열:
0 1 2 3 4 5
[1 3 2 8 6 4]
1) 루트 값 1을 반환값으로 저장
2) 마지막 값 4를 루트 자리로 이동
3) 마지막 원소 제거
중간 배열:
0 1 2 3 4
[(4) 3 2 8 6] <- 4가 루트 자리로 이동
// HeapifyDown 시작
- index 0(4), left=1(3), right=2(2)
가장 작은 자식은 2(index 2) → 4와 교환
0 1 2 3 4
[(2) 3 (4) 8 6]
- index 2의 자식 인덱스는 5, 6 (배열 길이 5에서 범위 밖)
더 이상 내려갈 수 없으므로 종료
최종 배열:
0 1 2 3 4
[2 3 4 8 6]- 이 과정에서도 전체 배열이 정렬되는 것은 아니지만, 새로운 최솟값 2가 다시 배열 0번 인덱스에 위치하게 됩니다. 삭제 연산 역시 힙의 높이에 비례하는 O(log N) 시간이 걸립니다.
4.4 Peek / Count / Clear
Peek는 삭제 없이 현재 최솟값만 확인하는 메서드입니다.
public T Peek()
{
if (_heap.Count == 0)
{
throw new InvalidOperationException("큐가 비어 있습니다.");
}
return _heap[0]; // 루트 반환
}- 배열 0번 인덱스에는 항상 최솟값이 오도록 유지되기 때문에, Peek는 O(1) 시간에 동작합니다.
Count는 내부 리스트의 개수를 그대로 반환하며, Clear는 리스트를 비워 PriorityQueue를 초기 상태로 돌립니다.
public int Count => _heap.Count;
public void Clear()
{
_heap.Clear();
}
4.5 Resize와 GC/성능 관점
PriorityQueue는 내부적으로 List<T>를 사용하므로, 원소가 늘어나면 리스트의 내부 배열 크기를 늘리기 위해 배열 재할당과 복사가 발생할 수 있습니다. 이 과정은 O(n) 비용이 들며, 큰 힙을 다룰 때는 성능에 영향을 줄 수 있습니다. 다만, 배열 크기 확장은 자주 일어나지 않고, 삽입·삭제 자체는 여전히 O(log N)에 동작합니다. 또한 힙은 노드를 개별적으로 할당하는 링크드 구조가 아니므로, GC 부담이 상대적으로 적고, 캐시 친화적인 접근 패턴을 가집니다.
게임처럼 프레임 타임이 민감한 환경에서는, PriorityQueue가 최대 어느 정도의 원소를 가질지 예상할 수 있다면 초기 용량(capacity)을 넉넉하게 설정해 두어 런타임 중 불필요한 Resize를 줄이는 것이 좋습니다.
정리하면, PriorityQueue의 핵심은 전체를 정렬하지 않고도 루트(배열 0번 인덱스)에 있는 최솟값만 항상 올바르게 유지하는 것이며, 이를 위해 삽입 시 HeapifyUp, 삭제 시 HeapifyDown을 통해 Min-Heap 규칙(부모 ≤ 자식)을 효율적으로 지켜 나가는 구조입니다.
5. C# 기반 PriorityQueue 직접 구현 코드
지금까지 HeapifyUp과 HeapifyDown의 동작을 단계별 예제와 함께 살펴보며 핵심 코드를 부분적으로 확인했습니다.
아래는 Min-Heap 기반 PriorityQueue의 전체 구현 코드로, 위에서 설명한 동작 흐름이 모두 하나의 클래스 안에 정리되어 있습니다. 또한 IComparer<T>를 생성자 인자로 전달하여 다양한 우선순위 정책(Min-Heap 또는 Max-Heap)을 적용할 수 있습니다.
using System;
using BCL = System.Collections.Generic; // BCL - Base Class Library
namespace Daebak.Common.Collections
{
/// <summary>
/// 우선순위 큐 (Min-Heap 기반)
/// </summary>
public class PriorityQueue<T>
{
private BCL.List<T> _heap; // 힙 노드들을 저장하는 동적 배열
private readonly BCL.IComparer<T> _cmp; // 우선순위 비교용 Comparer
public int Count => _heap.Count;
public PriorityQueue(BCL.IComparer<T> cmp = null)
{
_heap = new BCL.List<T>();
_cmp = cmp ?? BCL.Comparer<T>.Default; // 기본 Comparer 사용 (T가 IComparable이면 자동 적용)
}
/// <summary>
/// 원소 추가
/// </summary>
public void Enqueue(T item)
{
_heap.Add(item); // 마지막 위치에 추가
HeapifyUp(_heap.Count - 1); // 부모와 비교하며 위로 이동
}
/// <summary>
/// 최소값 제거 및 반환
/// </summary>
public T Dequeue()
{
if (_heap.Count == 0)
{
throw new InvalidOperationException("큐가 비어 있습니다.");
}
T root = _heap[0]; // 최소값(루트) 저장
int lastIndex = _heap.Count - 1;
_heap[0] = _heap[lastIndex]; // 마지막 노드를 루트로 이동
_heap.RemoveAt(lastIndex); // 마지막 노드 제거
if (_heap.Count > 0)
{
HeapifyDown(0); // 자식과 비교하며 아래로 이동
}
return root; // 최소값 반환
}
/// <summary>
/// 최소값 조회 (삭제하지 않음)
/// </summary>
public T Peek()
{
if (_heap.Count == 0)
{
throw new InvalidOperationException("큐가 비어 있습니다.");
}
return _heap[0]; // 루트 반환
}
/// <summary>
/// 모든 원소 제거
/// </summary>
public void Clear()
{
_heap.Clear();
}
private void HeapifyUp(int index)
{
// 삽입한 노드를 부모와 비교하여 올바른 위치까지 위로 이동
while (index > 0)
{
int parent = (index - 1) / 2;
// 부모보다 크거나 같으면(우선순위가 낮으면) 종료
if (_cmp.Compare(_heap[index], _heap[parent]) >= 0)
{
break;
}
Swap(index, parent); // 부모와 교환
index = parent; // 부모 위치로 갱신
}
}
private void HeapifyDown(int index)
{
// 루트에서 시작하여 자식들과 비교하며 내려가는 과정
int lastIndex = _heap.Count - 1;
while (true)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
int smallest = index;
// 왼쪽 자식이 더 작은 경우
if (left <= lastIndex && _cmp.Compare(_heap[left], _heap[smallest]) < 0)
{
smallest = left;
}
// 오른쪽 자식이 더 작은 경우
if (right <= lastIndex && _cmp.Compare(_heap[right], _heap[smallest]) < 0)
{
smallest = right;
}
// 더 이상 내려갈 필요 없음
if (smallest == index)
{
break;
}
Swap(index, smallest); // 더 작은 자식과 교환
index = smallest; // 위치 갱신
}
}
private void Swap(int a, int b)
{
// 두 인덱스의 값을 교환
T tmp = _heap[a];
_heap[a] = _heap[b];
_heap[b] = tmp;
}
}
}6. 유니티(Unity) 환경에서 테스트해 보기
Unity에서 PriorityQueue가 올바르게 동작하는지 간단히 확인해 보겠습니다. 아래 예제에서는 몇 개의 정수를 임의 순서로 Enqueue 한 뒤, 항상 가장 작은 값부터 Dequeue 되는지 로그로 확인합니다.
using UnityEngine;
using Daebak.Common.Collections;
public class Test_PriorityQueue : MonoBehaviour
{
void Start()
{
PriorityQueue<int> pq = new PriorityQueue<int>();
Debug.Log("Enqueue: 30, 10, 50, 20, 40");
pq.Enqueue(30);
pq.Enqueue(10);
pq.Enqueue(50);
pq.Enqueue(20);
pq.Enqueue(40);
Debug.Log($"Count: {pq.Count}");
Debug.Log($"Peek (최소값 미리 보기): {pq.Peek()}");
Debug.Log("Dequeue 순서:");
while (pq.Count > 0)
{
int value = pq.Dequeue();
Debug.Log(value);
}
Debug.Log($"Count after Dequeue: {pq.Count}");
}
}
실행 결과
Enqueue: 30, 10, 50, 20, 40
Count: 5
Peek (최소값 미리 보기): 10
Dequeue 순서:
10
20
30
40
50
Count after Dequeue: 0
삽입 순서는 30, 10, 50, 20, 40이었지만, Dequeue되는 순서는 항상 10 → 20 → 30 → 40 → 50처럼 오름차순(작은 값부터)이 되는 것을 확인할 수 있습니다. 이를 통해 Min-Heap 기반 PriorityQueue가 제대로 동작한다는 것을 검증할 수 있습니다.
마무리
PriorityQueue(우선순위 큐)는 “가장 먼저 들어온 데이터”가 아니라 “가장 중요한 데이터”를 우선적으로 처리해야 할 때 사용하는 자료구조입니다. 이번 글에서는 Min-Heap 기반 PriorityQueue의 구조, 동작 방식, 시간 복잡도, 그리고 C#과 Unity 환경에서의 실제 구현과 테스트 방법까지 살펴보았습니다.
게임 개발 실무에서는 경로 탐색, 이벤트 스케줄링, 타이머, AI 태스크 처리 등 다양한 영역에서 PriorityQueue를 적용할 수 있습니다. 직접 구현한 PriorityQueue를 프로젝트에 맞게 변형해 보면서, 우선순위 기반 처리 구조를 게임 로직에 자연스럽게 녹여 보는 것도 좋은 연습이 될 것입니다.
※ 다음 글에서는 Graph(그래프) 구조를 살펴보며, 노드와 간선으로 구성된 비선형 자료구조의 기본 개념과 표현 방식을 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Tree(트리) 구현 (0) | 2025.12.10 |
|---|---|
| Unity 개발자를 위한 Graph(그래프)의 이해 (0) | 2025.12.10 |
| Unity 개발자를 위한 C# Dictionary(딕셔너리) 구현 (0) | 2025.12.08 |
| Unity 개발자를 위한 C# HashSet(해시셋) 구현 (0) | 2025.12.07 |
| Unity 개발자를 위한 C# Deque(덱) 구현 (0) | 2025.12.06 |
