핵심 정리
| 연산 | 비용 | 의미 |
|---|---|---|
| peek | O(1) | 가장 우선순위 높은 값 확인 |
| enqueue | O(log n) | 새 값 추가 후 힙 조정 |
| dequeue | O(log n) | 루트 제거 후 힙 조정 |
| build heap | O(n) | 배열 전체를 힙으로 구성 |
csharp
var pq = new PriorityQueue<string, int>();
pq.Enqueue("B", 20);
pq.Enqueue("A", 10);
string first = pq.Dequeue(); // "A"구조
힙은 완전 이진 트리 형태를 유지하면서 부모와 자식 사이의 우선순위 규칙을 만족하는 자료구조입니다. 최소 힙에서는 부모가 자식보다 작거나 같습니다.
text
1
/ \
3 5
/ \
7 9힙은 전체가 정렬된 구조가 아닙니다. 오직 루트가 가장 작은 값이라는 보장만 있습니다. 그래서 최솟값을 반복해서 꺼내는 문제에는 좋지만, 임의 위치의 값을 정렬 순서로 탐색하는 데에는 맞지 않습니다.
배열로 표현
힙은 보통 배열로 표현합니다. 0-based index 기준으로 부모와 자식 위치를 계산할 수 있습니다.
text
parent = (i - 1) / 2
left = i * 2 + 1
right = i * 2 + 2삽입할 때는 끝에 넣고 위로 올리며, 삭제할 때는 마지막 값을 루트로 옮긴 뒤 아래로 내립니다.
언제 쓰나
| 상황 | 적합한 선택 |
|---|---|
| 매번 최솟값·최댓값 필요 | 우선순위 큐 |
| 최단 경로 후보 관리 | 다익스트라 |
| 상위 K개 유지 | 크기 K 힙 |
| 전체 정렬만 필요 | 정렬 API가 더 단순 |
| 임의 값 삭제가 잦음 | 별도 인덱스 관리 필요 |
C#의 PriorityQueue<TElement, TPriority>는 priority가 작은 항목을 먼저 꺼내는 최소 우선순위 큐입니다. 최댓값을 먼저 꺼내고 싶으면 priority를 음수로 넣거나 비교 기준을 별도로 설계합니다.
csharp
var maxPq = new PriorityQueue<int, int>();
maxPq.Enqueue(10, -10);
maxPq.Enqueue(30, -30);
int max = maxPq.Dequeue(); // 30주의할 점
우선순위 큐는 같은 priority의 dequeue 순서를 안정적으로 보장하는 정렬 큐가 아닙니다. 같은 우선순위의 순서가 중요하면 tie-breaker를 priority에 함께 넣거나 별도 순번을 관리해야 합니다.
또 PriorityQueue<TElement, TPriority>는 .NET 6 이상 API입니다. 제출 환경이 낮은 버전이면 직접 힙을 구현해야 할 수 있습니다.
참고 링크
1 sources