优先队列是一种基本的数据结构，它扩展了标准队列的功能，为每个元素分配一个优先级。与先进先出 (FIFO) 队列（元素按到达顺序处理）不同，优先队列根据元素的优先级进行出队（移除）操作。优先级最高的元素总是首先被处理。这种优先级可以基于数值（最小或最大），也可以基于任何自定义比较标准。
优先队列在许多算法和应用程序中都非常宝贵，在这些算法和应用程序中，基于重要性的任务或事件的有效管理至关重要。例如：
- 最短作业优先 (SJF) 调度：在操作系统中，根据进程的估计执行时间有效地调度进程。
- 最佳优先搜索算法 (A*，Dijkstra)：通过基于节点到目标的估计距离对节点进行优先级排序，在图中查找最佳路径。
- 事件模拟：在离散事件模拟中管理事件，确保首先处理最紧急的事件。
- 堆排序：一种利用堆（一种特殊的优先队列）的特性进行高效排序的排序算法。
- 霍夫曼编码：通过根据符号的频率对符号进行优先级排序来构建高效的压缩算法。
在 C# 中实现优先队列
C# 提供了几种实现优先队列的方法。让我们探讨两种常见的方法：
1. 使用 SortedSet
内置的 SortedSet 类提供了一种方便的实现优先队列的方法。SortedSet 自动将其元素保持在排序顺序，简化了优先级排序。当优先级由元素的自然排序隐式确定时（例如，整数），这尤其有用。
using System;
using System.Collections.Generic;
public class PriorityQueueSortedSet<T> where T : IComparable<T>
{
private SortedSet<T> _elements = new SortedSet<T>();
public void Enqueue(T item) => _elements.Add(item);
public T Dequeue()
{
if (_elements.Count == 0)
{
throw new InvalidOperationException("Priority queue is empty.");
}
T item = _elements.Min;
_elements.Remove(item);
return item;
}
public bool IsEmpty() => _elements.Count == 0;
public int Count => _elements.Count;
}
此实现很简单，但其性能受底层 SortedSet 的限制，SortedSet 为入队和出队操作提供 O(log n) 的复杂度。内存使用量也可能相对较高，尤其是在大型数据集的情况下。
2. 实现最小堆
为了提高性能，尤其是在大型数据集的情况下，自定义最小堆实现提供了显著的优势。最小堆是一种二叉树结构，它始终确保最小的元素位于根部，从而为入队和出队操作提供 O(log n) 的复杂度。虽然比 SortedSet 更复杂，但最小堆提供了卓越的性能和对内存管理的细粒度控制。
(本文档不包含详细的最小堆实现，但网上有很多资源可用。)
实现比较
| 特性 | SortedSet |
最小堆 |
|---|---|---|
| 易用性 | 更容易 | 更难 |
| 入队/出队性能 | O(log n) | O(log n) |
| 内存使用量 | 可能更高 | 可能更低 |
| 灵活性 | 较低 | 较高 |
选择合适的实现
SortedSet 和自定义最小堆之间的最佳选择取决于您的具体要求。对于简单的应用程序，如果易于实现比极端性能更重要，则 SortedSet 是理想的选择。对于性能关键型应用程序或大型数据集，自定义最小堆实现在速度和内存效率方面提供了显著的优势。