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.