var pq = new PriorityQueue<string, int>();
pq.Enqueue("B", 20);
pq.Enqueue("A", 10);

string first = pq.Dequeue(); // "A"

구조

힙은 완전 이진 트리 형태를 유지하면서 부모와 자식 사이의 우선순위 규칙을 만족하는 자료구조입니다. 최소 힙에서는 부모가 자식보다 작거나 같습니다.

        1
      /   \
     3     5
    / \
   7   9

힙은 전체가 정렬된 구조가 아닙니다. 오직 루트가 가장 작은 값이라는 보장만 있습니다. 그래서 최솟값을 반복해서 꺼내는 문제에는 좋지만, 임의 위치의 값을 정렬 순서로 탐색하는 데에는 맞지 않습니다.

배열로 표현

힙은 보통 배열로 표현합니다. 0-based index 기준으로 부모와 자식 위치를 계산할 수 있습니다.

parent = (i - 1) / 2
left   = i * 2 + 1
right  = i * 2 + 2

삽입할 때는 끝에 넣고 위로 올리며, 삭제할 때는 마지막 값을 루트로 옮긴 뒤 아래로 내립니다.

언제 쓰나

C#의 PriorityQueue<TElement, TPriority>는 priority가 작은 항목을 먼저 꺼내는 최소 우선순위 큐입니다. 최댓값을 먼저 꺼내고 싶으면 priority를 음수로 넣거나 비교 기준을 별도로 설계합니다.

var descending = Comparer<int>.Create((a, b) => b.CompareTo(a));
var maxPq = new PriorityQueue<int, int>(descending);
maxPq.Enqueue(10, 10);
maxPq.Enqueue(30, 30);

int max = maxPq.Dequeue(); // 30

priority를 음수로 바꾸는 방식은 int.MinValue를 반전할 때 overflow가 날 수 있습니다. 비교자를 넘기면 priority 값 자체의 의미를 유지할 수 있습니다. 비어 있을 가능성이 있으면 예외를 던지는 Peek·Dequeue 대신 TryPeek·TryDequeue를 씁니다.

while (pq.TryDequeue(out string? element, out int priority))
{
    Console.WriteLine($"{element}: {priority}");
}

pq.EnqueueRange(new[]
{
    (Element: "A", Priority: 10),
    (Element: "B", Priority: 20)
});

string removed = pq.EnqueueDequeue("C", 15); // C를 넣은 뒤 최솟값 하나를 바로 꺼냄

TryDequeue는 빈 큐에서 false를 반환하고 element와 priority를 함께 받을 수 있습니다. EnqueueRange는 여러 element-priority 쌍을 넣을 때, EnqueueDequeue는 넣은 뒤 즉시 최솟값 하나를 제거해야 할 때 두 번의 호출보다 효율적일 수 있습니다. 둘 다 일반 Enqueue·Dequeue와 결과 순서가 같다는 전제를 먼저 확인하고 사용하세요.

주의할 점