在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。可以根據需要修改代碼來實現最大堆或者自定義優先級的堆。