Dotnet C# PriorityQueue

.Net PriorityQueue

今天來學習一下在 .Net6 才終於提供的 PriorityQueue，先到 Github上面查看一下原始碼

/// <typeparam name="TElement">Specifies the type of elements in the queue.</typeparam>
/// <typeparam name="TPriority">Specifies the type of priority associated with enqueued elements.</typeparam>
public class PriorityQueue<TElement, TPriority>

使用方法也與 Queue 相同，加入 Queue 使用 Enqueue 方法，移出 Queue 使用 Dequeue 方法，查看第一個元素使用 Peek 方法
不過 PriorityQueue 使用前需要先指定元素的類型(TElement)以及優先度(TPriority)

舉例來說有一組使用者 User1、User2、User3 優先度分別是 1、2、3

User1 1
User2 2
User3 3

首先我們建立一個 PriorityQueue 類型為 String 順序使用 Int

var pQueue = new PriorityQueue<string, int>();
	
pQueue.Enqueue("User1", 1);
pQueue.Enqueue("User2", 2);
pQueue.Enqueue("User3", 3);

這時我們可以使用 Peek方法來看一下目前誰位於首要元素

pQueue.Peek();

User1

這邊回傳的結果是 User1，那為什麼是是回傳 User1 呢？
我們可以先看看原始碼 這邊 PriorityQueue 提供了許多的 Constructor ，我們今天使用的是 Default Constructor

public PriorityQueue()
{
    _nodes = Array.Empty<(TElement, TPriority)>();
    _comparer = InitializeComparer(null);
}

這邊除了賦值了一個空的 Array ，下方還呼叫了一個 InitializeComparer 的方法，原始碼

private static IComparer<TPriority>? InitializeComparer(IComparer<TPriority>? comparer)
{
    if (typeof(TPriority).IsValueType)
    {
        if (comparer == Comparer<TPriority>.Default)
        {
            // if the user manually specifies the default comparer,
            // revert to using the optimized path.
            return null;
  
        return comparer;
    }
    else
    {
        // Currently the JIT doesn't optimize direct Comparer<T>.Default.Compare
        // calls for reference types, so we want to cache the comparer instance instead.
        // TODO https://github.com/dotnet/runtime/issues/10050: Update if this changes in the future.
        return comparer ?? Comparer<TPriority>.Default;
    }
}

到這邊就很清楚了，此方法會檢查你有沒有要使用自己寫的 Comparer，如果沒有的的話就使用類型預設的 Comparer
以我們的例子來看我們 TPriority 使用的類型是 Int32 所以最後使用的是 Int32 裡面的 CompareTo

Console.WriteLine(0.CompareTo(1));
Console.WriteLine(1.CompareTo(1));
Console.WriteLine(2.CompareTo(1));

-1
0
1

所以呼叫 PriorityQueue 的 Enqueue 方法時就會比較 int 的大小，如果數字比較小的話比較結果會回傳 -1
所以這時 Enqueue 方法就會知道這個新插入的元素是比目前第一個元素優先度更高，這就是為什麼一開始的範例回傳的是 User1

知道原理後我們也可以試試其他類型，例如前幾天使用的字串比較方法 StringComparer.Ordinal 也剛好是一個 Comparer

var spQueue = new PriorityQueue<string, string>(StringComparer.Ordinal);
	
spQueue.Enqueue("User1", "aGroup");
spQueue.Enqueue("User2", "bGroup");
spQueue.Enqueue("User3", "AGroup");

這次我們在 Constructor 直接指定我們要使用 StringComparer.Ordinal， 並且我們知道此比較方法是使用 ASCII 進行比較 結果也如設想回傳的是 user3

pQueue.Peek();

user3

還有一點需要注意順序的調整會在 Enqueue 和 Dequeue 方法中進行，並且只會跟第一節點進行比較 例如在新增一個 "User4" "BGroup"，正常來說 BGroup 會比 aGroup 和 bGroup 優先度高，不過它目前的位置並不會在第二優先位置反而會在最後一位

var spQueue = new PriorityQueue<string, string>(StringComparer.Ordinal);
	
spQueue.Enqueue("User1", "aGroup");
spQueue.Enqueue("User2", "bGroup");
spQueue.Enqueue("User3", "AGroup");
spQueue.Enqueue("User4", "BGroup");

Console.WriteLine(spQueue);

IReadOnlyCollection<ValueTuple<String,String>> (4 items)•••
Item1	Item2
User3	AGroup
User2	bGroup
User1	aGroup
User4	BGroup

這時我們先呼叫一次 Dequeue 方法把 User3 移除，最後在檢查一次 這時 User4 又會回到第一優先位置了，畢竟 Queue 的特性也確實沒必要完全保持 Collection 順序的正確性

spQueue.Dequeue();
Console.WriteLine(spQueue);

IReadOnlyCollection<ValueTuple<String,String>> (3 items)•••
Item1	Item2
User4	BGroup
User2	bGroup
User1	aGroup

---

Summary

今天學習了 PriorityQueue 的使用方法，跟 Queue 相比之下多了一個優先度的概念
有了這個特性我們可以拿來做一些需要優先執行的相關功能，類似VIP等相關功能需要優先執行的群體的任務
就可以使用到PriorityQueue