백준 문제를 풀다가 우선순위 큐 자료구조를 사용해야하는 문제를 접하게 되었다.
C#에서 우선순위큐를 사용하기 위해서 두가지 방법을 찾아보았다. 이 두가지 방법을 알아보기 전에 우선순위 큐란 무엇인가부터 정리해보자.

우선순위 큐

우선순위 큐(Priority Queue)는 일반 큐와 이름은 비슷하지만 동작하는 방식이 다르다.
우선순위 큐의 각 원소(데이터)는 저마다의 우선순위를 가지고 있으며 들어간 순서에 상관없이 높은 우선순위를 가진 원소가 순서대로 나온다는 특징이 있다.

첫번째 방법 - SortedSet 이용

C#의 SortedSet 자료구조를 이용한 우선순위 큐 구현이다.
Set이기 때문에 중복값은 처리할 수 없다는 단점이 있다.

 public class Mycompare : IComparer
{	
    // 어떻게 정렬할건지 Compare 함수를 정의하면 된다.
    public int Compare(string x, string y)
    {
        return x.Length - y.Length
    }
}    

SortedSet 자료구조를 어떻게 정렬할 것인지에 대한 Compare 클래스를 정의하여 SortedSet을 생성할때 Compare 클래스를 인자로 사용한다.

SortedSet<string> priority_queue = new SortedSet<string>(new Mycompare());

두번째 방법 - 리스트 이용

우선순위 큐를 리스트로 구현한 것이다.

public class PriorityQueue<T>
{
    private List<T> data;
    private Func<T, T, int> comparer;

    public int Count => data.Count;

    public bool IsEmpty() => data.Count == 0;

    public PriorityQueue()
    {
        data = new List<T>();
        comparer = Comparer<T>.Default.Compare;
    }

    public PriorityQueue(Func<T, T, int> customComparer)
    {
        data = new List<T>();
        comparer = customComparer;
    }

    public void Enqueue(T item)
    {
        data.Add(item);
        int currentIndex = data.Count - 1;

        while (currentIndex > 0)
        {
            int parentIndex = (currentIndex - 1) / 2;
            if (comparer(data[currentIndex], data[parentIndex]) >= 0)
                break;

            SwapElements(currentIndex, parentIndex);
            currentIndex = parentIndex;
        }
    }

    public T Dequeue()
    {
        if (data.Count == 0)
            throw new InvalidOperationException("Priority queue is empty.");

        int lastIndex = data.Count - 1;
        T frontItem = data[0];
        data[0] = data[lastIndex];
        data.RemoveAt(lastIndex);

        lastIndex--;
        int parentIndex = 0;

        while (true)
        {
            int leftChildIndex = parentIndex * 2 + 1;

            if (leftChildIndex > lastIndex)
                break;

            int rightChildIndex = leftChildIndex + 1;
            if (rightChildIndex <= lastIndex && comparer(data[rightChildIndex], data[leftChildIndex]) < 0)
                leftChildIndex = rightChildIndex;

            if (comparer(data[parentIndex], data[leftChildIndex]) <= 0)
                break;

            SwapElements(parentIndex, leftChildIndex);
            parentIndex = leftChildIndex;
        }

        return frontItem;
    }

    public T Peek()
    {
        if (data.Count == 0)
            throw new InvalidOperationException("Priority queue is empty.");
        return data[0];
    }

    private void SwapElements(int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
}

참고
링크1
링크2