C# PriorityQueue 優先佇列介紹

在 C# 10 (.NET 6 或以上)增加了 PriorityQueue，每個元素都會依照優先等級離開佇列

基本示範

需要指定兩個類型，第一個是放入佇列的內容，第二個是該內容的優先度，越小的越優先。

    
PriorityQueue<string, int> queue = new();

queue.Enqueue("A1", 1);
queue.Enqueue("B1", 2);
queue.Enqueue("C1", 3);
queue.Enqueue("A2", 1);
queue.Enqueue("B2", 2);
queue.Enqueue("C2", 3);

while (queue.Count > 0)
{
     var item = queue.Dequeue();
     Console.WriteLine(item);
}

/*
範例輸出:
A1
A2
B2
B1
C1
C2
*/
    

不過由上面輸出可以發現有個和我們預想的不太一樣的地方，就是 PriorityQueue 和一般佇列不同，在優先等級相同的情況下不是先進先出。不過後面我們會介紹解決的方法。

使用列舉(enum)

數字不容易記得，我們可以將優先度替換為 enum

    
/// <summary>
/// 會員等級
/// </summary>
public enum Status
{
    /// <summary>
    /// 金牌會員
    /// </summary>
    Gold = 1,

    /// <summary>
    /// 銀牌會員
    /// </summary>
    Silver = 2,

    /// <summary>
    /// 一般會員
    /// </summary>
    Normal = 3,
}

    

    
PriorityQueue<string, Status> queue = new();

queue.Enqueue("A1", Status.Gold);
queue.Enqueue("B1", Status.Silver);
queue.Enqueue("C1", Status.Normal);
queue.Enqueue("A2", Status.Gold);
queue.Enqueue("B2", Status.Silver);
queue.Enqueue("C2", Status.Normal);

while (queue.Count > 0)
{
    var item = queue.Dequeue();
    Console.WriteLine($"{item}");
}

/*
範例輸出:
A1
A2
B2
B1
C1
C2
*/
    

解決沒有先進先出的問題

其實有個非常簡單的方式，就是將「優先度」變為兩個屬性(使用 Tuple)，增加時間戳記:

    
PriorityQueue<string, (Status, DateTime)> queue = new();

queue.Enqueue("A1", (Status.Gold, DateTime.Now));
queue.Enqueue("B1", (Status.Silver, DateTime.Now));
queue.Enqueue("C1", (Status.Normal, DateTime.Now));
queue.Enqueue("A2", (Status.Gold, DateTime.Now));
queue.Enqueue("B2", (Status.Silver, DateTime.Now));
queue.Enqueue("C2", (Status.Normal, DateTime.Now));

while (queue.Count > 0)
{
    var item = queue.Dequeue();
    Console.WriteLine($"{item}");
}

/*
範例輸出:
A1
A2
B1
B2
C1
C2
*/
    

自訂比較器

假設今天已經訂好金牌會員的值或是分數是 10，銀牌會員 5，一般會員是 1，不能更改，而預設的情況下是越小的月優先，該怎麼辦？很簡單，我們可以自訂比較器

    
/// <summary>
/// 會員等級
/// </summary>
public enum Status
{
    /// <summary>
    /// 金牌會員
    /// </summary>
    Gold = 10,

    /// <summary>
    /// 銀牌會員
    /// </summary>
    Silver = 5,

    /// <summary>
    /// 一般會員
    /// </summary>
    Normal = 1,
}
    

    
/// <summary>
/// 自訂比較器
/// </summary>
public class StatusComparer : IComparer<(Status, DateTime)>
{
    public int Compare((Status, DateTime) x, (Status, DateTime) y)
    {
        if (x.Item1 == y.Item1) return x.Item2.CompareTo(y.Item2);
        return y.Item1.CompareTo(x.Item1);
    }
}
    

    

PriorityQueue<string, (Status, DateTime)> queue = new(new StatusComparer());

queue.Enqueue("A1", (Status.Gold, DateTime.Now));
queue.Enqueue("B1", (Status.Silver, DateTime.Now));
queue.Enqueue("C1", (Status.Normal, DateTime.Now));
queue.Enqueue("A2", (Status.Gold, DateTime.Now));
queue.Enqueue("B2", (Status.Silver, DateTime.Now));
queue.Enqueue("C2", (Status.Normal, DateTime.Now));

while (queue.Count > 0)
{
    var item = queue.Dequeue();
    Console.WriteLine($"{item}");
}

/*
範例輸出:
A1
A2
B1
B2
C1
C2
*/
    

參考資料：
Microsoft.learn - PriorityQueue<TElement,TPriority> Class