C#中實現(xiàn)PriorityQueue優(yōu)先級隊列的代碼
前言
前段時間看到有大佬對.net 6.0新出的PriorityQueue(優(yōu)先級隊列)數(shù)據(jù)結(jié)構(gòu)做了解析,但是沒有源碼分析,所以本著探究源碼的心態(tài),看了看并分享出來。它不像普通隊列先進先出(FIFO),而是根據(jù)優(yōu)先級出隊。
ps:讀者多注意代碼的注釋。
D叉樹的認識(d-ary heap)
首先我們在表示一個堆(大頂堆或小頂堆)的時候,實際上是通過一個一維數(shù)組來維護一個二叉樹(d=2,d表示每個父節(jié)點最多有幾個子節(jié)點),首先看下圖的二叉樹,數(shù)字代表索引:
任意一個節(jié)點的父節(jié)點的索引為:(index - 1) / d任意一個節(jié)點的左子節(jié)點的索引為:(index * d) + 1任意一個節(jié)點的右子節(jié)點的索引為:(index * d) + 2它的時間復(fù)雜度為O(logndn)
通過以上公式,我們就可以輕松通過一個數(shù)組來表達一個堆,只需保證能拿到正確的索引即可進行快速的插入和刪除。
源碼解析
構(gòu)造初始化
關(guān)于這部分主要介紹關(guān)鍵的字段和方法,比較器的初始化以及堆的初始化,請看如下代碼:
public class PriorityQueue<TElement, TPriority> { /// <summary> /// 保存所有節(jié)點的一維數(shù)組且每一項是個元組 /// </summary> private (TElement Element, TPriority Priority)[] _nodes; /// <summary> /// 優(yōu)先級比較器,這里用的泛型,比較器可以自己實現(xiàn) /// </summary> private readonly IComparer<TPriority>? _comparer; /// <summary> /// 當(dāng)前堆的大小 /// </summary> private int _size; /// <summary> /// 版本號 /// </summary> private int _version; /// <summary> /// 代表父節(jié)點最多有4個子節(jié)點,也就是d=4(d=4時好像效率最高) /// </summary> private const int Arity = 4; /// <summary> /// 使用位運算符,表示左移2或右移2(效率更高),即相當(dāng)于除以4, /// </summary> private const int Log2Arity = 2; /// <summary> /// 構(gòu)造函數(shù)初始化堆和比較器 /// </summary> public PriorityQueue() { _nodes = Array.Empty<(TElement, TPriority)>(); _comparer = InitializeComparer(null); } /// <summary> /// 重載構(gòu)造函數(shù),來定義比較器否則使用默認的比較器 /// </param> public PriorityQueue(IComparer<TPriority>? comparer) { _nodes = Array.Empty<(TElement, TPriority)>(); _comparer = InitializeComparer(comparer); } private static IComparer<TPriority>? InitializeComparer(IComparer<TPriority>? comparer) { //如果是值類型,如果是默認比較器則返回null if (typeof(TPriority).IsValueType) { if (comparer == Comparer<TPriority>.Default) { return null; } return comparer; } //否則就使用自定義的比較器 else { return comparer ?? Comparer<TPriority>.Default; } } /// <summary> /// 獲取索引的父節(jié)點 /// </summary> private int GetParentIndex(int index) => (index - 1) >> Log2Arity; /// <summary> /// 獲取索引的左子節(jié)點 /// </summary> private int GetFirstChildIndex(int index) => (index << Log2Arity) + 1; }
單元總結(jié):
- 實際所有元素使用一維數(shù)組來維護這個堆。
- 調(diào)用方可以自定義比較器,但是類型得一致。
- 如果沒有比較器,則使用默認的比較器。
- 默認一個父節(jié)點最多有4個子節(jié)點,D=4時效率好像是最好的。
- 獲取父節(jié)點索引位置和子節(jié)點索引位置使用位運算符,效率更高。
入隊操作
入隊操作操作相對簡單,主要是做擴容和插入處理,請看如下代碼:
public void Enqueue(TElement element, TPriority priority) { //拿到最大位置的索引,然后再將數(shù)組長度+1 int currentSize = _size++; _version++; //如果長度相等,說明已經(jīng)到達最大位置,數(shù)組需要擴容了才能容下更多的元素 if (_nodes.Length == currentSize) { //擴容,參數(shù)是代表數(shù)組最小容量 Grow(currentSize + 1); } if (_comparer == null) { MoveUpDefaultComparer((element, priority), currentSize); } else { MoveUpCustomComparer((element, priority), currentSize); } } private void Grow(int minCapacity) { //增長倍數(shù) const int GrowFactor = 2; //每次擴容的最小值 const int MinimumGrow = 4; //每次擴容都2倍擴容 int newcapacity = GrowFactor * _nodes.Length; //數(shù)組不能大于最大長度 if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength; //使用他們兩個的最大值 newcapacity = Math.Max(newcapacity, _nodes.Length + MinimumGrow); //如果比參數(shù)小,則使用參數(shù)的最小值 if (newcapacity < minCapacity) newcapacity = minCapacity; //重新分配內(nèi)存,設(shè)置大小,因為數(shù)組的保存在內(nèi)存中是連續(xù)的 Array.Resize(ref _nodes, newcapacity); } private void MoveUpDefaultComparer((TElement Element, TPriority Priority) node, int nodeIndex) { //nodes保存副本 (TElement Element, TPriority Priority)[] nodes = _nodes; //這里入隊操作是從空閑索引第一個位置開始插入 while (nodeIndex > 0) { //找父節(jié)點索引位置 int parentIndex = GetParentIndex(nodeIndex); (TElement Element, TPriority Priority) parent = nodes[parentIndex]; //插入節(jié)點和父節(jié)點比較,如果小于0(默認比較器情況下構(gòu)建的小頂堆),則交換位置 if (Comparer<TPriority>.Default.Compare(node.Priority, parent.Priority) < 0) { nodes[nodeIndex] = parent; nodeIndex = parentIndex; } //算是性能優(yōu)化吧,不必檢查所有節(jié)點,當(dāng)發(fā)現(xiàn)大于時,就直接退出就可以了 else { break; } } //將插入節(jié)點放到它應(yīng)該的位置 nodes[nodeIndex] = node; }
單元總結(jié):
- 首先記錄當(dāng)前元素最大的索引位置,根據(jù)適當(dāng)?shù)那闆r來擴容。
- 擴容正常情況下是以2倍的增長速度擴容。
- 插入數(shù)據(jù)時,從最后一個節(jié)點的父節(jié)點向上還是找,比較元素的Priority,交換位置,默認情況下是構(gòu)建小頂堆。
出隊操作
出隊操作簡單來說就是將根元素返回并移除(也就是數(shù)組的第一個元素),然后根據(jù)比較器將最小或最大的元素放到堆頂,請看如下代碼:
public TElement Dequeue() { if (_size == 0) { throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue); } //將堆頂元素返回 TElement element = _nodes[0].Element; //然后調(diào)整堆 RemoveRootNode(); return element; } private void RemoveRootNode() { //記錄最后一個元素的索引位置,并且將堆的大小-1 int lastNodeIndex = --_size; _version++; if (lastNodeIndex > 0) { //堆的大小已經(jīng)被減1,所以將最后一個元素作為副本,開始從堆頂重新整理堆 (TElement Element, TPriority Priority) lastNode = _nodes[lastNodeIndex]; if (_comparer == null) { MoveDownDefaultComparer(lastNode, 0); } else { MoveDownCustomComparer(lastNode, 0); } } if (RuntimeHelpers.IsReferenceOrContainsReferences<(TElement, TPriority)>()) { //將最后一個位置的元素設(shè)置為默認值 _nodes[lastNodeIndex] = default; } } private void MoveDownDefaultComparer((TElement Element, TPriority Priority) node, int nodeIndex) { (TElement Element, TPriority Priority)[] nodes = _nodes; //堆的實際大小 int size = _size; int i; //當(dāng)左子節(jié)點的索引小于堆的實際大小時 while ((i = GetFirstChildIndex(nodeIndex)) < size) { //左子節(jié)點元素 (TElement Element, TPriority Priority) minChild = nodes[i]; //當(dāng)前左子節(jié)點的索引 int minChildIndex = i; //這里即找到所有同一個父節(jié)點的相鄰子節(jié)點,但是要判斷是否超出了總的大小 int childIndexUpperBound = Math.Min(i + Arity, size); //按照索引區(qū)間順序查找,并根據(jù)比較器找到最小的子元素位置 while (++i < childIndexUpperBound) { (TElement Element, TPriority Priority) nextChild = nodes[i]; if (Comparer<TPriority>.Default.Compare(nextChild.Priority, minChild.Priority) < 0) { minChild = nextChild; minChildIndex = i; } } //如果最后一個節(jié)點的元素,比這個最小的元素還小,那么直接放到父節(jié)點即可 if (Comparer<TPriority>.Default.Compare(node.Priority, minChild.Priority) <= 0) { break; } //將最小的子元素賦值給父節(jié)點 nodes[nodeIndex] = minChild; nodeIndex = minChildIndex; } //將最后一個節(jié)點放到空閑出來的索引位置 nodes[nodeIndex] = node; }
單元總結(jié):
- 返回根節(jié)點元素,然后移除根節(jié)點元素,調(diào)整堆。
- 從根節(jié)點開始,依次查找對應(yīng)父節(jié)點的所有子節(jié)點,放到堆頂,也就是數(shù)組索引0的位置,然后如果樹還有層數(shù),繼續(xù)循環(huán)查找。
- 將最后一個元素放到堆適當(dāng)?shù)奈恢?,然后再將最后一個位置的元素置為默認值。
總結(jié)
通過源碼的解讀,除了了解類的設(shè)計之外,更對對優(yōu)先級隊列數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)有了更加深刻和清晰的認識。
這里也只是粘貼出主要的代碼,需要看詳細代碼的請點擊這里,筆者可能有一些解讀錯誤的地方,歡迎評論指正。
到此這篇關(guān)于C#中PriorityQueue(優(yōu)先級隊列)的實現(xiàn)的文章就介紹到這了,更多相關(guān)C#優(yōu)先級隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C#使用WebService結(jié)合jQuery實現(xiàn)無刷新翻頁的方法
這篇文章主要介紹了C#使用WebService結(jié)合jQuery實現(xiàn)無刷新翻頁的方法,涉及C#中WebService與jQuery操作的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-04-04C#使用Consul集群進行服務(wù)注冊與發(fā)現(xiàn)
這篇文章主要介紹了C#使用Consul集群進行服務(wù)注冊與發(fā)現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12WPF利用WindowChrome實現(xiàn)自定義窗口
這篇文章主要為大家詳細介紹了WPF如何利用WindowChrome實現(xiàn)自定義窗口,文中的示例代碼講解詳細,具有一定的借鑒價值,需要的可以參考一下2023-02-02