欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C#中實(shí)現(xiàn)PriorityQueue優(yōu)先級(jí)隊(duì)列的代碼

 更新時(shí)間:2021年12月30日 10:48:23   作者:CNBLOG  
這篇文章主要介紹了C#中PriorityQueue優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn),構(gòu)造初始化這部分主要介紹關(guān)鍵的字段和方法,比較器的初始化以及堆的初始化,需要的朋友可以參考下

前言

前段時(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é):

  1. 實(shí)際所有元素使用一維數(shù)組來維護(hù)這個(gè)堆。
  2. 調(diào)用方可以自定義比較器,但是類型得一致。
  3. 如果沒有比較器,則使用默認(rèn)的比較器。
  4. 默認(rèn)一個(gè)父節(jié)點(diǎn)最多有4個(gè)子節(jié)點(diǎn),D=4時(shí)效率好像是最好的。
  5. 獲取父節(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結(jié)合jQuery實(shí)現(xiàn)無刷新翻頁的方法,涉及C#中WebService與jQuery操作的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
    2015-04-04
  • OpenXml合并Table單元格代碼實(shí)例

    OpenXml合并Table單元格代碼實(shí)例

    在本篇文章里小編給大家整理了關(guān)于OpenXml合并Table單元格的相關(guān)實(shí)例詳解,需要的朋友們參考下。
    2019-08-08
  • C#通過反射獲取當(dāng)前工程中所有窗體并打開的方法

    C#通過反射獲取當(dāng)前工程中所有窗體并打開的方法

    這篇文章主要介紹了C#通過反射獲取當(dāng)前工程中所有窗體并打開的方法,涉及C#針對(duì)窗體的獲取與顯示等操作技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
    2015-08-08
  • 解答“60k”大佬的19道C#面試題(上)

    解答“60k”大佬的19道C#面試題(上)

    這篇文章主要解答了“60k”大佬的19道C#面試題中的10道,文中的面試題比較小眾,作者給了不錯(cuò)的答案,相信對(duì)你以后的面試有所幫助,感興趣就來了解下
    2020-06-06
  • C#使用Winform編寫一個(gè)圖片預(yù)覽器管理

    C#使用Winform編寫一個(gè)圖片預(yù)覽器管理

    這篇文章主要為大家詳細(xì)介紹了C#如何使用Winform編寫一個(gè)通用圖片預(yù)覽器管理,包含滾輪放大縮小,剪切,下一頁,方向變化等,需要的可以參考下
    2024-02-02
  • C#隨機(jī)數(shù)生成字母金字塔

    C#隨機(jī)數(shù)生成字母金字塔

    這篇文章主要為大家詳細(xì)介紹了C#隨機(jī)數(shù)生成字母金字塔,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-11-11
  • C#使用Consul集群進(jìn)行服務(wù)注冊(cè)與發(fā)現(xiàn)

    C#使用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-12
  • C#獲取文件名和文件路徑的兩種實(shí)現(xiàn)方式

    C#獲取文件名和文件路徑的兩種實(shí)現(xiàn)方式

    這篇文章主要介紹了C#獲取文件名和文件路徑的兩種實(shí)現(xiàn)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • c#:CTS類型系統(tǒng)

    c#:CTS類型系統(tǒng)

    CTS通用類型系統(tǒng),是.Net中一套定義類型的規(guī)則。我們要掌握c#開發(fā),首先要建立這個(gè)類型概念,只有知道c#的元素是什么類型,才能進(jìn)行相關(guān)的分析和選材。
    2012-12-12
  • WPF利用WindowChrome實(shí)現(xiàn)自定義窗口

    WPF利用WindowChrome實(shí)現(xiàn)自定義窗口

    這篇文章主要為大家詳細(xì)介紹了WPF如何利用WindowChrome實(shí)現(xiàn)自定義窗口,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,需要的可以參考一下
    2023-02-02

最新評(píng)論