C# PriorityQueue的enqueue

C# PriorityQueue的enqueue方法用于将元素插入到优先队列中。其实现方式通常是将新元素添加到队列末尾，然后根据优先级重新排列队列中的元素，使得队列中优先级最高的元素在队首。

下面是一个简单的C# PriorityQueue实现，其中enqueue方法的代码如下：

public void Enqueue(T item, int priority)
{
    elements.Add(new Element<T>(item, priority));
    elements.Sort();
}

其中，elements是一个List<Element<T>>类型的成员变量，Element<T>是一个封装了元素和优先级的结构体，根据优先级实现了IComparable接口的CompareTo方法。

在enqueue方法中，我们首先将新元素添加到队列末尾，然后调用List的Sort方法进行排序，以确保队列中优先级最高的元素在队首。

相关问题

c# PriorityQueue

C# doesn't have a built-in implementation of a PriorityQueue, but you can create one using various data structures. One common approach is to use a MinHeap or MaxHeap along with a Dictionary to track the priority of each element.

Here's an example implementation of a PriorityQueue in C#:

using System;
using System.Collections.Generic;

public class PriorityQueue<T>
{
    private readonly List<T> elements;
    private readonly Dictionary<T, int> priorities;

    public int Count => elements.Count;

    public PriorityQueue()
    {
        elements = new List<T>();
        priorities = new Dictionary<T, int>();
    }

    public void Enqueue(T element, int priority)
    {
        elements.Add(element);
        priorities[element] = priority;
        HeapifyUp(elements.Count - 1);
    }

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

        T frontElement = elements[0];
        elements[0] = elements[Count - 1];
        elements.RemoveAt(Count - 1);
        priorities.Remove(frontElement);
        HeapifyDown(0);

        return frontElement;
    }

    public bool Contains(T element)
    {
        return priorities.ContainsKey(element);
    }

    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (priorities[elements[parentIndex]] <= priorities[elements[index]])
                break;

            Swap(parentIndex, index);
            index = parentIndex;
        }
    }

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

            int smallestChildIndex = index;

            if (leftChildIndex < Count && priorities[elements[leftChildIndex]] < priorities[elements[smallestChildIndex]])
                smallestChildIndex = leftChildIndex;

            if (rightChildIndex < Count && priorities[elements[rightChildIndex]] < priorities[elements[smallestChildIndex]])
                smallestChildIndex = rightChildIndex;

            if (smallestChildIndex == index)
                break;

            Swap(index, smallestChildIndex);
            index = smallestChildIndex;
        }
    }

    private void Swap(int index1, int index2)
    {
        T tempElement = elements[index1];
        elements[index1] = elements[index2];
        elements[index2] = tempElement;

        priorities[elements[index1]] = index1;
        priorities[elements[index2]] = index2;
    }
}

You can use the PriorityQueue like this:

PriorityQueue<int> priorityQueue = new PriorityQueue<int>();
priorityQueue.Enqueue(3, 2);
priorityQueue.Enqueue(1, 1);
priorityQueue.Enqueue(5, 3);

while (priorityQueue.Count > 0)
{
    int element = priorityQueue.Dequeue();
    Console.WriteLine(element);
}

This will output:

1
3
5

Note that this implementation assumes the elements are of a type that supports comparison using the `<` and `>` operators. If your elements are custom objects, you may need to implement the `IComparable<T>` interface or provide a custom comparer.

c# PriorityQueue命名空间

在 C# 中，PriorityQueue 可以通过使用 System.Collections.Generic 命名空间下的 PriorityQueue 类来实现。需要注意的是，PriorityQueue 类并不是 C# 标准库中的一部分，因此需要使用第三方库或者自己实现该类。

以下是一个使用 System.Collections.Generic 命名空间下的 PriorityQueue 类的示例代码：

using System;
using System.Collections.Generic;

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

    public PriorityQueue()
    {
        this.data = new List<T>();
    }

    public void Enqueue(T item)
    {
        data.Add(item);
        int ci = data.Count - 1; // child index; start at end
        while (ci > 0)
        {
            int pi = (ci - 1) / 2; // parent index
            if (data[ci].CompareTo(data[pi]) >= 0)
                break; // child item is larger than (or equal) parent so we're done
            T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;
            ci = pi;
        }
    }

    public T Dequeue()
    {
        // assumes pq is not empty; up to calling code
        int li = data.Count - 1; // last index (before removal)
        T frontItem = data[0];   // fetch the front
        data[0] = data[li];
        data.RemoveAt(li);

        --li; // last index (after removal)
        int pi = 0; // parent index. start at front of pq
        while (true)
        {
            int ci = pi * 2 + 1; // left child index of parent
            if (ci > li) break;  // no children so done
            int rc = ci + 1;     // right child
            if (rc <= li && data[rc].CompareTo(data[ci]) < 0)
                ci = rc; // prefer smallest child
            if (data[pi].CompareTo(data[ci]) <= 0)
                break; // parent is smaller than (or equal to) smallest child so done
            T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp; // swap parent and child
            pi = ci;
        }
        return frontItem;
    }

    public int Count
    {
        get { return data.Count; }
    }

    public override string ToString()
    {
        string s = "";
        for (int i = 0; i < data.Count; ++i)
            s += data[i].ToString() + " ";
        s += "count = " + data.Count;
        return s;
    }

    public bool IsConsistent()
    {
        // is the heap property true for all data?
        if (data.Count == 0) return true;
        int li = data.Count - 1; // last index
        for (int pi = 0; pi < data.Count; ++pi) // each parent index
        {
            int lci = 2 * pi + 1; // left child index
            int rci = 2 * pi + 2; // right child index

            if (lci <= li && data[pi].CompareTo(data[lci]) > 0) return false; // if lc exists and it's greater than parent then bad.
            if (rci <= li && data[pi].CompareTo(data[rci]) > 0) return false; // check the right child too.
        }
        return true; // passed all checks
    }
}

以上代码实现了一个基本的 Priority Queue 类，可以用于存储任意实现了 IComparable<T> 接口的类型。在该类中，Enqueue() 方法用于将元素加入队列，Dequeue() 方法用于取出队首元素并移除，Count 属性返回队列中元素数量，IsConsistent() 方法用于检查队列是否符合堆的定义。