在刷 LeetCode 等题库的时候，我们经常遇到使用堆（Heap）的情况，在 C++ 中可以直接使用 STL 的实现，在 Java 中可以使用 Priority Queue，但是在 C# 10之前的版本并不直接提供这样的实现。
P.S. 在 C# 10 中，新增加了优先队列的官方实现，详见 PriorityQueue<TElement,TPriority> 类 。
一种可行的解决办法 （适用于 C# Version < 10）
C# 集合类的思想和 C++、Java 并不一致（提供尽可能多的集合类以满足需求），C# 只提供基础的通用集合类。
所以如果想要在 C# 中使用 Heap/Priority Queue，要么使用第三方库实现，要么自己基于 SortedList、SortedSet、SortedDictionary 构造一个功能类似的（或者直接去用 C++ 或者 Java 吧）。
至少在 C# 9.0 中还未提供，不确定将来的 C# 是否会提供 Priority Queue
下面附上一种基于 SortedList 构建的 Priority Queue：
1public class PriorityQueue<T> where T : IComparable<T> {
2 private SortedList<T, int> list = new SortedList<T, int>();
3 private int count = 0;
4
5 public void Add(T item) {
6 if (list.ContainsKey(item)) list[item]++;
7 else list.Add(item, 1);
8
9 count++;
10 }
11
12 public T PopFirst() {
13 if (Size() == 0) return default(T);
14 T result = list.Keys[0];
15 if (--list[result] == 0)
16 list.RemoveAt(0);
17
18 count--;
19 return result;
20 }
21
22 public T PopLast() {
23 if (Size() == 0) return default(T);
24 int index = list.Count - 1;
25 T result = list.Keys[index];
26 if (--list[result] == 0)
27 list.RemoveAt(index);
28
29 count--;
30 return result;
31 }
32
33 public int Size() {
34 return count;
35 }
36
37 public T PeekFirst() {
38 if (Size() == 0) return default(T);
39 return list.Keys[0];
40 }
41
42 public T PeekLast() {
43 if (Size() == 0) return default(T);
44 int index = list.Count - 1;
45 return list.Keys[index];
46 }
47}
版权声明：本文遵循 CC BY-SA 4.0 版权协议，转载请附上原文出处链接和本声明。
Copyright statement: This article follows the CC BY-SA 4.0 copyright agreement. For reprinting, please attach the original source link and this statement.