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