C#中PriorityQueue怎么实现-开发者知识库平台

C#中PriorityQueue怎么实现

1069

2023/12/12 3:13:03

栏目: 编程语言

在C#中，可以使用堆（Heap）来实现PriorityQueue。堆是一种特殊的二叉树结构，满足以下性质：

完全二叉树：除了最后一层，其他层的节点数都是满的，最后一层的节点都靠左排列。
堆序性：对于最大堆，父节点的值大于等于其子节点的值；对于最小堆，父节点的值小于等于其子节点的值。

在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。可以根据需要修改代码来实现最大堆或者自定义优先级的堆。

辰迅云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

C#中PriorityQueue怎么实现

最新知识库

相关标签