C# 힙(Heap)이란?

소개

C#에서 힙은 우선순위 큐(priority queue)를 구현하는 데 사용되는 자료구조 중 하나입니다. 우선순위 큐는 요소들이 들어온 순서와 상관없이 우선순위에 따라 처리해야 하는 경우에 유용하게 사용됩니다. 힙은 배열(array)을 기반으로 하며, 다양한 그래프 알고리즘에서 최단 경로를 찾는 데 활용됩니다. 이번 글에서는 C# 힙(heap)에 대한 정의, 구현 방법, 연산, 활용 등에 대해 자세히 살펴보겠습니다.

힙이란?

힙은 이진 트리(binary tree)를 기반으로 한 자료구조입니다. 이진 트리에서는 각 노드가 최대 두 개의 자식 노드를 가질 수 있지만, 힙에서는 각 노드가 최대 두 개의 자식 노드를 가지며, 트리의 루트 노드는 언제나 최소값 또는 최대값을 가집니다. 최소 힙에서는 루트 노드가 최소값을 가지며, 각 노드의 자식 노드는 부모 노드보다 큰 값을 가집니다. 최대 힙에서는 루트 노드가 최대값을 가지며, 각 노드의 자식 노드는 부모 노드보다 작은 값을 가집니다. 이러한 성질은 힙을 우선순위 큐(priority queue)를 구현하는 데 사용할 수 있도록 만듭니다.

힙의 구현

힙은 일반적으로 배열을 사용하여 구현됩니다. 배열에서는 각 노드가 인덱스(index)로 식별되며, 부모 노드와 자식 노드의 관계는 다음과 같이 표현됩니다.

- 부모 노드의 인덱스 = (자식 노드의 인덱스 - 1) / 2
- 왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2) + 1
- 오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2) + 2

힙에서 삽입(insertion) 연산은 항상 새로운 노드를 배열의 끝에 추가하고, 그 후에 부모 노드와 비교하여 위치를 조정합니다. 삭제(deletion) 연산은 일반적으로 최소값 또는 최대값을 배열의 첫 번째 노드와 교환한 후, 첫 번째 노드를 삭제하고 부모 노드와 비교하여 위치를 조정합니다. 탐색(peeking) 연산은 배열의 첫 번째 노드를 반환합니다.

힙의 연산

힙에서는 주로 다음과 같은 연산이 수행됩니다.

• 삽입(insertion): 새로운 요소를 힙에 추가합니다.
• 삭제(deletion): 최소값 또는 최대값을 힙에서 제거합니다.
• 탐색(peeking): 최소값 또는 최대값을 반환합니다.

힙의 활용

힙은 우선순위 큐(priority queue)를 구현하는 데 사용됩니다. 우선순위 큐는 요소들이 들어온 순서와 상관없이 우선순위에 따라 처리해야 하는 경우에 유용하게 사용됩니다. 또한, 힙은 다익스트라 알고리즘(Dijkstra's algorithm) 등의 그래프 알고리즘에서 최단 경로를 찾는 데 활용됩니다.

C# 힙의 활용 예시

C#에서는 System.Collections.Generic 네임스페이스에서 Heap 클래스를 제공합니다. 이 클래스는 최소 힙(min heap)을 구현하는 데 사용됩니다. 예를 들어, 다음과 같이 우선순위 큐를 구현할 수 있습니다.

using System.Collections.Generic;

class PriorityQueue<T>
{
    private Heap<T> heap = new Heap<T>();

    public void Enqueue(T item, int priority)
    {
        heap.Insert(new PriorityQueueItem<T>(item, priority));
    }

    public T Dequeue()
    {
        return heap.RemoveMin().Item;
    }
}

class PriorityQueueItem<T> : IComparable<PriorityQueueItem<T>>
{
    public T Item { get; private set; }
    public int Priority { get; private set; }

    public PriorityQueueItem(T item, int priority)
    {
        Item = item;
        Priority = priority;
    }

    public int CompareTo(PriorityQueueItem<T> other)
    {
        return Priority.CompareTo(other.Priority);
    }
}

위 코드에서는 Heap 클래스를 이용하여 PriorityQueue 클래스를 구현합니다. PriorityQueueItem 클래스는 우선순위 큐에 저장될 요소를 나타내며, 우선순위를 가지고 있습니다.

결론

C#에서 힙은 우선순위 큐를 구현하는 데 사용되는 중요한 자료구조 중 하나입니다. 힙은 최소 힙과 최대 힙으로 나뉘며, 일반적으로 배열을 사용하여 구현됩니다. 또한, 힙은 다양한 그래프 알고리즘에서 최단 경로를 찾는 데 활용됩니다. 이번 글을 통해 C# 힙(heap)에 대해 더욱 자세히 알아보았습니다.