当前位置: 首页 > news >正文

wordpress主页音乐/seol英文啥意思

wordpress主页音乐,seol英文啥意思,自己做的网站打开太慢,协同开发平台原创公众号:bigsai,码字不易,如有帮助,记得三联!前言在个人的专栏中,其他排序陆陆续续都已经写了,而堆排序迟迟没有写,在国庆假期的尾声,把堆排序也写一写。插入类排序—(折半)插入排…

原创公众号:bigsai,码字不易,如有帮助,记得三联!

前言

在个人的专栏中,其他排序陆陆续续都已经写了,而堆排序迟迟没有写,在国庆假期的尾声,把堆排序也写一写。

插入类排序—(折半)插入排序、希尔排序
交换类排序—冒泡排序、快速排序手撕图解
归并类排序—归并排序(逆序数问题)
计数排序引发的围观风波——一种O(n)的排序
两分钟搞懂桶排序

对于常见的快排、归并这些O(nlogn)的排序算法,我想大部分人可能很容易搞懂,但是堆排序大部分人可能比较陌生,或许在Java的comparator接口中可能了解一点。但堆排序在应用中比如优先队列此类维护动态数据效率比较高,有着非常广泛的应用。

而堆排序可以拆分成排序,其中你可能对堆比较陌生,对排序比较熟悉,下面就带你彻底了解相关内容。

9e500ee92f2b65c008c790963c6dd453.png

什么是堆?

谈起堆,很多人第一联想到的是土堆,而在数据结构中这种土堆与完全二叉树更像,而堆就是一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树(完全)的数组对象。且总是满足以下规则:

  • 堆总是一棵完全二叉树
  • 每个节点总是大于(或小于)它的孩子节点。

完全二叉树
我想什么是完全二叉树大部分人也是知道:最后一层以上都是满的,最后一层节点从左到右可以排列(有任何空缺即不满足完全二叉树)。

177e37b61f27ff1e13ed17ef7b8d831e.png

看作树的数组对象
我们都知道我们排序的对象一般都是对数组之类的序列进行排序,如果转成抽象数据结构再实现可能成本比较大。

我们正常在构造一棵二叉树的时候通常采用链式left,right节点,但其实二叉树的表示方式用数组也可以实现,只不过普通的二叉树如果用数组储存可能空间利用 效率会很低而很少采用,但我们的堆是一颗完全二叉树。使用数组储存空间使用效率也比较高,所以在形式上我们把这个数组看成对应的完全二叉树,而操作上可以直接操作数组也比较方便。

9e818862329bf0f9a34e702bf915b5d3.png

大根堆 VS 小根
上面还有一点就是在这个完全二叉树中所有节点均大于(或小于)它的孩子节点,所以这里就分为两种情况

  • 如果所有节点大于孩子节点值,那么这个堆叫做大根堆,堆的最大值在根节点。
  • 如果所有节点小于孩子节点值,那么这个堆叫做小根堆,堆的最小值在根节点。
bbda31f9ae9d15c479a7f9f5fdafa8ef.png

堆排序

通过上面的介绍,我想你对堆应该有了一定的认识,堆排序肯定是借助堆实现的某种排序,其实堆排序的整体思路也很简单,就是

  • 构建堆,取堆顶为最小(最大)。
  • 将剩下的元素重新构建一个堆,取堆顶,一直到元素取完为止。

建堆

如果给一个无序的序列,首先要给它建成一个堆,我们如何实现这个操作呢?以下拿一个小根堆为例进行分析。

对于二叉树(数组表示),我们从下往上进行调整,从第一个非叶子节点开始向前调整,对于调整的规则如下:

①对于小根堆,当前节点与左右孩子比较,如果均小于左右孩子节点,那么它本身就是一个小根堆,它不需要做任何改变,如果左右有孩子节点比它还小,那么就要和最小的那个进行替换。

ef8e34378485f25460af535115ba1ef6.png


②但是普通节点替换可能没问题,对于某些和子节点替换有可能改变子树成堆,所以需要继续往下判断交换(最差判断到叶子节点)。

592d8148991bc1459b99bf725e8ffb43.png


分析构造堆的这个过程,每个非叶子节点都需要判断比较是否交换,这样一层就是O(n),而每个节点可能替换之后影响子节点成堆需要再往下判断遍历,你可能会认为它是一个O(nlogn),但其实你看看二叉树性值,大部分都是在底部的,上面的只有很少个数,如果你用数学方法去求得最终的复杂度它还是一个O(n)级别,这里就不作详细介绍了。

一个大根堆建立过程也是一样的:

28566a0f727b8f99f5e197b39a602c3c.gif

堆排序

上面的一个堆建造完毕之后,我们怎么去利用这个堆实现排序呢?答案也是很简单的,我们知道堆有一个特性就是堆顶是最小(或最大),而我们建造这个如果去除第一个元素,剩余左右孩子依然满足堆的性质

f2c3418d1d6bb649bddb7a72b5676eae.png


最后一个元素放置堆顶,由于第一个元素的存在使得整个不满足堆的性质。分析这个结构,和我们前面构造堆的过程中构造到第一个元素的操作相同:

  • 判断左右孩子,如果需要交换则交换,交换后再次考虑交换子节点是否需要交换。一直到不需要考虑。
6b41e88e741974e32e4979095edfa8c7.png


这样到最后,堆排序即可完成,最终得到的序列即为堆排序序列。

一个大根堆的排序过程如下:

a2e441eabe7aef799aa5706a85474fe5.gif

具体实现

有了上述的思想之后,如何具体的实现这个堆排序的代码呢?
从细致的流程来看,大概流程是如下的:

给定数组建堆(creatHeap)

  • 从第一个非叶子节点开始判断交换下移(shiftDown),使得当前节点和子孩子能够保持堆的性值
  • 如果交换打破子孩子堆结构性质,那么就要重新下移(shiftDown)被交换的节点一直到停止。

堆构造完成,取第一个堆顶元素为最小(最大),剩下左右孩子依然满足堆的性值,但是缺个堆顶元素,如果给孩子调上来,可能会调动太多并且可能破坏堆结构。

  • 所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown),不过需要注意此时整个堆的大小已经发生了变化,我们在逻辑上不会使用被抛弃的位置,所以在设计函数的时候需要附带一个堆大小的参数。
  • 重复以上操作,一直堆中所有元素都被取得停止。

而堆算法复杂度的分析上,之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换,每个个数最坏为logn个。这样复杂度就为O(nlogn).总的时间复杂度为O(n)+O(nlogn)=O(nlogn).

具体实现的代码如下:

import java.util.Arrays;public class 堆排序 {    static void swap(int arr[],int m,int n)    {        int team=arr[m];        arr[m]=arr[n];        arr[n]=team;    }    //下移交换 把当前节点有效变换成一个堆(小根)    static void shiftDown(int arr[],int index,int len)//0 号位置不用    {        int leftchild=index*2+1;//左孩子        int rightchild=index*2+2;//右孩子        if(leftchild>=len)            return;        else if(rightchild

执行结果:

f6ab956d41e8401cb27d643e6f40b10f.png

当然,代码为了成章节我把它命名为中文,还有些不规范的地方请注意甄别。

结语

对于堆排序就先介绍到这里了,当然堆的强大之处不止这么一点,优先队列同样也是用到堆但是这里就不详细介绍了,我相信优秀的你肯定又掌握了一门O(nlogn)级别的排序算法啦。如果写的有啥不确切地方还请指正。

最后,如果感觉不错一键三联哦!,欢迎关注公众号:bigsai,更多精彩等你来看。期待你的关注,并且笔者也准备了一波pdf学习资源分享给你。

e2d9ad9b3b17284e649aeb3c49508de3.png
http://www.lbrq.cn/news/827965.html

相关文章:

  • 网站建设公司彩铃/百度里面的站长工具怎么取消
  • 做推广网站那里好/信息推广
  • 东莞网站推广哪里好/百度竞价点击价格公式
  • 如何运用网站做推广/semikron
  • 网站 实施/写软文一篇多少钱合适
  • 武汉做网站公司hlbzx/网站检测工具
  • 西宁网站开发多少钱/搜索推广平台
  • 成都网站建设托管/宁波网站关键词优化代码
  • js网站源码/免费的自媒体一键发布平台
  • 做试题的网站/山西seo
  • 凡科做的网站提示证书错误/信息发布网站有哪些
  • 网站建设推广费用/枸橼酸西地那非片是什么
  • 网站建设付款页面/自己怎么创建网站
  • 移动门网站建设/哪个推广网站好
  • 长沙公司制作网站费用/怎么优化关键词
  • 网站建设尺寸像素是多少/日本进口yamawa
  • 做网站能赚钱/网站推广网络营销
  • 威海专业做网站设计的公司/全国疫情实时动态
  • 广告投放媒体/公司seo
  • 微信网站建设费用计入什么科目/app推广拉新一手渠道
  • 国外网站怎么做/企业内训课程
  • 湖北黄石域名注册网站建设/网络营销网
  • 互诺科技做网站怎么样/怎么推广产品最有效
  • 有没有适合宝妈找工作做兼职的网站/成都网络推广外包公司哪家好
  • 梵克雅宝官网中国官方网站/百度直接打开
  • 中牟建设委员会网站/网站建设网络推广平台
  • 网站建设哪几家好一些/现在有什么推广平台
  • 住房和城乡建设部网站资质查询/磁力吧ciliba
  • mysol做的选课网站/免费网页制作网站
  • javaweb做音乐网站/网站交易
  • MyBatis Plus高效开发指南
  • NISP-PTE基础实操——XSS
  • OpenCV 入门知识:图片展示、摄像头捕获、控制鼠标及其 Trackbar(滑动条)生成!
  • 7-大语言模型—指令理解:指令微调训练+模型微调
  • KVM中使用桥接模式.运维就业技术教程
  • 【MATLAB例程】Taylor算法用于TOA(到达时间)的三维标签位置解算,可自适应基站数量。附下载链接