C#でPriorityQueueを実装する方法は何ですか。

2年 ago
陽, 向宇
1 minute

C#では、PriorityQueueを実装するためにヒープ（Heap）を使用することができます。ヒープは特殊な二分木構造であり、以下の性質を満たします。

  1. 完全二分木：最後のレベルを除いて、全てのレベルのノードの数が満たされ、最後のレベルのノードは左に配置されています。
  2. 堆の順序性：最大ヒープの場合、親ノードの値は子ノードの値以上である；最小ヒープの場合、親ノードの値は子ノードの値以下である。

C#では、ヒープを表すために配列を使用することができます。ヒープの特性に基づいて、ノードの親ノードや子ノードを簡単な数学演算で見つけることができます。

以下是一个使用数组实现最小堆PriorityQueue的示例代码：

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> heap;

    public PriorityQueue()
    {
        heap = new List<T>();
    }

    public int Count => heap.Count;

    public void Enqueue(T item)
    {
        heap.Add(item);
        HeapifyUp(heap.Count - 1);
    }

    public T Dequeue()
    {
        if (heap.Count == 0)
        {
            throw new InvalidOperationException("PriorityQueue is empty");
        }

        T firstItem = heap[0];
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        HeapifyDown(0);

        return firstItem;
    }

    private void HeapifyUp(int index)
    {
        int parentIndex = (index - 1) / 2;

        while (index > 0 && heap[index].CompareTo(heap[parentIndex]) < 0)
        {
            Swap(index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    private void HeapifyDown(int index)
    {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallestChildIndex = index;

        if (leftChildIndex < heap.Count && heap[leftChildIndex].CompareTo(heap[smallestChildIndex]) < 0)
        {
            smallestChildIndex = leftChildIndex;
        }

        if (rightChildIndex < heap.Count && heap[rightChildIndex].CompareTo(heap[smallestChildIndex]) < 0)
        {
            smallestChildIndex = rightChildIndex;
        }

        if (smallestChildIndex != index)
        {
            Swap(index, smallestChildIndex);
            HeapifyDown(smallestChildIndex);
        }
    }

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

上記のコードでは、要素を格納するためにListを使用しています。Enqueueメソッドは、まず要素をListの末尾に追加し、その後ヒープの性質に基づいて上方演算（HeapifyUp）を行います。Dequeueメソッドは、まずヒープの先頭要素（つまり最小要素）を取り出し、最後の要素をヒープの先頭に配置し、その後ヒープの性質に基づいて下方演算（HeapifyDown）を行います。

これにより、配列を使用して最小ヒープを実装したPriorityQueueが実現できました。必要に応じてコードを変更して、最大ヒープやカスタム優先度のヒープを実装することができます。

bannerAds