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

算法之堆排序

       堆排序是一种基于比较的排序算法,通过构建二叉堆(Binary Heap),可以利用堆的性质进行高效的排序。二叉堆是一个完全二叉树,可以有最大堆和最小堆两种形式。在最大堆中,父节点的值总是大于或等于其子节点的值;在最小堆中,父节点的值总是小于或等于其子节点的值。

先了解原理 

       在最大堆中,每次操作都会选出当前堆中的最大元素。这个元素被放置到堆的顶部,然后与数组的最后一个元素交换位置。交换后,该元素从堆中移除,因为它已经被放置在其最终位置。接下来,我们重新调整剩余的堆结构,以确保堆的最大元素位于顶部,为下一次操作做准备。通过不断重复这个过程,我们能够逐步构建出一个有序的数组。同理,小堆也是一样的

当然实际编程的时候要考虑式子

R[V]>=R[2V]  , R[V]>=R[2V+1]

咱们话不多说直接看题吧。

看题的时候先思考参数,v代表什么,n代表什么?v是根节点编号,n是堆的元素数。

i=v,都是根节点编号,R[0]=R[i],就是将根节点存到R[0]。根据式子R[V]>=R[2V]  , R[V]>=R[2V+1]

所以可以知道j=2*i   是出于什么目的了吧。

然后就是if判断j<=n应该很容易理解吧,因为n是总的堆的数目,j肯定要小于或者等于n的

至于那个if(j<n&&R[j]<R[j+1])  j++

这个很好理解,就是简单的将下面节点最大的用j表示,怎么说呢,就是你想想一颗二叉树,左节点是3,而右节点是4,而大堆肯定是选大的和根节点比较。所以才有这个if判断,如果右节点大,就让这个j++,让它指向右节点

然后就是那个空,明显是R[j] >=R[0]   ,因为前面已经将R[0]=R[i],所以这里和R[0]进行比较就行了。

然后第二个空,肯定是构建大堆呗,Heapify(R,i,n),第三个空 i>1或i>=2,第四个空是R[1]=R[0]。

相关文章:

  • 量子密钥分发系统基础器件(一):光纤干涉仪
  • C#算数运算符
  • HBase安装
  • 【深入浅出:正则化在防止深度学习过拟合中的应用】
  • AURIX TC3xx单片机介绍-启动过程介绍3
  • 【OpenGL Mathematics(GLM)下载链接】
  • 系统思考—决策
  • Vue组件通讯$attrs和$listeners例子
  • java新特性(Stream API)
  • 【RuoYi】使用代码生成器完成CRUD操作
  • 香橙派OrangePi AIpro,助力国产AIoT迈向新的台阶!
  • 阿里开源React应用动效解决方案:ant-motion
  • C语言#include<>和#include““有什么区别?
  • 【算法】位运算算法——丢失的数字
  • Flutter 中的 BaseLine 小部件:全面指南
  • 实现windows 窗体的自己画,网上摘抄的,学习了
  • 《深入 React 技术栈》
  • 【5+】跨webview多页面 触发事件(二)
  • android图片蒙层
  • JavaScript新鲜事·第5期
  • laravel 用artisan创建自己的模板
  • MySQL的数据类型
  • sublime配置文件
  • 对话 CTO〡听神策数据 CTO 曹犟描绘数据分析行业的无限可能
  • 翻译:Hystrix - How To Use
  • 高度不固定时垂直居中
  • 个人博客开发系列:评论功能之GitHub账号OAuth授权
  • 工程优化暨babel升级小记
  • 和 || 运算
  • 基于HAProxy的高性能缓存服务器nuster
  • 记一次和乔布斯合作最难忘的经历
  • 学习笔记:对象,原型和继承(1)
  • elasticsearch-head插件安装
  • 摩拜创始人胡玮炜也彻底离开了,共享单车行业还有未来吗? ...
  • 如何正确理解,内页权重高于首页?
  • ​LeetCode解法汇总2304. 网格中的最小路径代价
  • ​渐进式Web应用PWA的未来
  • ​虚拟化系列介绍(十)
  • ## 临床数据 两两比较 加显著性boxplot加显著性
  • #if 1...#endif
  • (04)Hive的相关概念——order by 、sort by、distribute by 、cluster by
  • (1)Nginx简介和安装教程
  • (2)(2.10) LTM telemetry
  • (2)关于RabbitMq 的 Topic Exchange 主题交换机
  • (C语言)球球大作战
  • (c语言版)滑动窗口 给定一个字符串,只包含字母和数字,按要求找出字符串中的最长(连续)子串的长度
  • (附源码)springboot助农电商系统 毕业设计 081919
  • (附源码)计算机毕业设计SSM保险客户管理系统
  • (附源码)计算机毕业设计SSM在线影视购票系统
  • (十三)Maven插件解析运行机制
  • (十五)devops持续集成开发——jenkins流水线构建策略配置及触发器的使用
  • (算法)求1到1亿间的质数或素数
  • (一)UDP基本编程步骤
  • (转) SpringBoot:使用spring-boot-devtools进行热部署以及不生效的问题解决
  • (转)拼包函数及网络封包的异常处理(含代码)