最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • NET6中的优先队列是怎么实现的呢?(组图)

    在最近发布的 .NET 6 中,包含了一个新的数据结构,即优先级队列 PriorityQueue。事实上,这种数据结构在 Java 中已经存在很多年了。优先队列是如何实现的?让我们一起来了解一下。

    时间复杂度

    因为接下来要分析时间复杂度,这里是几个时间复杂度的对比图,从低到高:O(1), O(logn), O(n), O(nlogn) , O(n2)。

    什么是优先队列

    首先,众所周知,队列是一种非常基础的数据结构,其特点是先进先出(FIFO)。

    优先级队列不一定是先进先出的,因为每个元素都有一个权重值,代表要出队的元素的优先级。

    队列可以用数组和链表来实现,简单高效,入队和出队的时间复杂度为O(1).

    优先队列可以用上面的方法吗?也是可以的,但是每次有新元素加入到队列中,都需要遍历并与队列中的元素进行比较,然后插入到合适的位置,这样整个序列可以保持从大到小或从小到大,入队时间复杂。度变成O(n),出队复杂度不变,或者O(1)。O(n)表示加入队列的时间线性增加,效率低。有没有更有效的方法??

    堆的数据结构有很多应用场景。最经典的一种是堆排序。堆排序是一种时间复杂度为 O(nlog n) 的原位排序算法。另外,堆也很适合做一个优先级队列。

    堆和树的结构实际上是相似的。有二叉堆、d-ary 堆、2-3 堆、斐波那契堆等等。堆的特点之一是每个父节点都大于或等于其子节点。,这是一个大的顶堆,或者每个父节点都小于等于它的子节点堆排序算法时间复杂度,这是一个小的顶堆,其他堆的儿子是左右的。其中,java中的PriorityQueue是用二进制小顶堆实现的。

    上面是二叉堆,.NET 6中的PriorityQueue是通过d-ary堆实现的,d表示父节点有几个子节点。在.NET 6中,这个值被指定为4,是一个小顶堆,也是“四管齐下的小顶堆”

    Quad heap 比 binary heap 快,你可以参考下面链接的论文

    优先级队列的回归基础实证研究

    那么如何在代码中实现呢?事实上,数组可以用来存储堆。我们可以通过“广度优先遍历”的方式将堆的节点映射到一个数组中,如下

    另外,堆和数组还有如下关系

    堆的顶点是数组的第一个也是最小的元素。

    通过子节点的下标,可以通过公式计算出父节点的下标,公式为

    P = (C – 1) / 4

    其中 P = 父节点的下标,C = 子节点的下标

    既然确定了优先级队列的数据结构堆排序算法时间复杂度,我们再来看看元素的入队和出队。

    入队入队

    使用堆实现优先队列,入队操作2步完成,非常简单!

    将新节点添加到末尾

    通过上面的公式P = (C – 1) / 4,将新的子节点的大小与父节点进行比较,如果子节点较小,则与父节点交换,此过程一直重复,直到子节点大于或等于父节点,或者子节点成为堆顶,堆就完成了,这个交换过程是自下而上的,进入的时间复杂度队列为 O(log n)。

    出队

    出队就是每次取队列中最小的元素。基于小顶堆结构,其实只需要取堆顶的元素,对应数组array[0]的第一个元素。

    你会发现,当顶部元素被移除时,小顶堆的顶部是空的。为了保持堆的结构,我们需要重新堆。

    类似于上述入队入队的逻辑。我们可以把堆的最后一个元素,放到堆的最上面,然后比较父节点和四个子节点的大小。如果大于子节点,则交换。重复这个过程,直到父节点大于四个子节点,或者到达堆的最后一层,堆就完成了。这个交换过程是自上而下的,出队的时间复杂度也是 O(log n) 。

    此外,如果多个子节点小于父节点,则交换父节点和最小的子节点。

    胀缩机制

    优先级队列是一个数组实现的四管齐下的小顶堆,所以存在数组的伸缩。

    扩容:最小为4,当阵列满时,会扩容到当前容量的两倍。

    Shrink:数组不会自动收缩,但是可以手动调用 TrimExcess() 方法。当空闲空间大于 10% 时,数组的长度会收缩到当前队列元素的数量。

    总结

    本文主要介绍.NET 6新的数据结构优先队列,有兴趣的也可以看看PriorityQueue的源码。其实就是基于堆的结构来实现的,也展示了入队和出队的堆结构的变化过程。 ,另外需要注意的是堆的结构是不稳定的,因为在排序的过程中,有一个堆的最后一个节点和堆顶节点交换的操作,所以优先级相同的元素不保证排队。以相同的顺序出队。

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » NET6中的优先队列是怎么实现的呢?(组图)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论