[C# Reference] 우선순위 큐 ( Priority Queue ) + Heap

DataClass PriorityQueue

    // 데이터 추가해서 사용
    public class DataClass
    {
        public int cost;

        public DataClass(int cost)
        {
            this.cost = cost;
        }
    }

    // DataClass의 cost를 기준으로 가장 작은 값을 우선으로 두는 우선순위 큐
    public class PriorityQueue
    {
        private List<DataClass> heap = new List<DataClass>();

        public int Count => heap.Count;

        public void Enqueue(DataClass data)
        {
            heap.Add(data);
            int now = heap.Count - 1; // 추가한 노드 위치

            while (now > 0)
            {
                int next = (now - 1) / 2; // 부모 노드 (트리)
                
                if (heap[now].cost > heap[next].cost)
                    break;
                
                // 부모노드보다 추가한게 같거나 작으면 Swap
                DataClass temp = heap[now];
                heap[now] = heap[next];
                heap[next] = temp;
                now = next;
            }
        }

        public DataClass Dequeue()
        {
            DataClass ret = heap[0]; // 리턴 값
            int lastIndex = heap.Count - 1;
            heap[0] = heap[lastIndex];
            heap.RemoveAt(lastIndex);
            lastIndex -= 1;
            int now = 0;

            while (true)
            {
                int left = 2 * now + 1;
                int right = 2 * now + 2;
                int next = now;

                // 왼쪽보다 크면 왼쪽으로 보내기
                if (left <= lastIndex && heap[next].cost > heap[left].cost)
                    next = left;

                // 오른쪽보다 크면 오른쪽으로 보내기
                if (right <= lastIndex && heap[next].cost > heap[right].cost)
                    next = right;

                if (next == now)
                    break;

                DataClass temp = heap[now];
                heap[now] = heap[next];
                heap[next] = temp;

                now = next;
            }

            return ret;
        }
    }

PriorityQueue<T>

// 최소 값을 우선으로 두는 우선순위 큐
public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> heap = new List<T>();

    public int Count => heap.Count;

    public void Enqueue(T data)
    {
        heap.Add(data);
        int now = heap.Count - 1; // 추가한 노드 위치

        while (now > 0)
        {
            int next = (now - 1) / 2; // 부모 노드 (트리)

            if (heap[now].CompareTo(heap[next]) > 0)
                break;

            // 부모노드보다 추가한게 같거나 작으면 Swap
            T temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            now = next;
        }
    }

    public T Dequeue()
    {
        T ret = heap[0]; // 리턴 값
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        lastIndex -= 1;
        int now = 0;

        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;
            int next = now;

            // 왼쪽보다 크면 왼쪽으로 보내기
            if (left <= lastIndex && heap[next].CompareTo(heap[left]) > 0)
                next = left;

            // 오른쪽보다 크면 오른쪽으로 보내기
            if (right <= lastIndex && heap[next].CompareTo(heap[right]) > 0)
                next = right;

            if (next == now)
                break;

            T temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;

            now = next;
        }

        return ret;
    }
}