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