【算法基础(四)】堆排序(二)
堆排序(二)
把数组从零开始连续的一段 = 完全二叉树 size
i 左 son 2*1+1
i 右 son 2*1+2
父 (i-1) / 2
堆是完全二叉树,分为大根堆和小根堆
在完全二叉树里,每一棵子数最大的值是头节点的值,就是大根堆
同理,在完全二叉树里,每一棵子数最小的值是头节点的值,就是小根堆
大根堆排序,插入的值 和 父节点比较,如果比父节点大,和它交换,直到最大,就停止,通过这样的调整,得到的一定是大根堆。这个过程,我们叫做 heapInsert
public static void heapInsert(int [] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {// 和父节点交换值 并且把当前下标移动到父节点swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; }
}
从一堆数中找出最大值,移除它,保持还是大根堆,我们管这个过程叫做heapify
public static void heapify(int [] arr, int index, int heapSize) {int left = index * 2 + 1; // 左孩子的下标while (left < heapSize) { // 下方还有孩子 (左孩子越界,那么就没有右孩子了。)// 俩个孩子中,谁的值大,把下标给谁 (先找出孩子中最大的)int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1:left;// 父和孩子之间,谁的值大,把下标给谁 (较大的孩子和父节点找出最大的)largest = arr[largest] > arr[index] ? largest : index;if (largest == index) { // 如果当前节点就是最大的 跳出break;}swap(arr, largest, index); // 交换位置index = largest; // 继续比较left = index * 2 + 1; // 找左孩子继续 while}
}
题目:
已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离可以不超过K,并且K相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
假如K = 6 ,建立一个heapSize = 7 的小根堆 (这样小根堆的最小值一定是数组的最小值)
把最小的弹出,保持小根堆,新加入的数字做heapfiy,
继续上面的步骤,直到全部弹出。
public static void main(String[] args) {PriorityQueue<Integer> heap = new PriorityQueue<>();heap.add(8);heap.add(4);heap.add(10);heap.add(3);while(!heap.isEmpty) {System.out.println(heap.poll());}
}
相关文章:
【算法基础(四)】堆排序(二)
堆排序(二) 把数组从零开始连续的一段 完全二叉树 size i 左 son 2*11 i 右 son 2*12 父 (i-1) / 2 堆是完全二叉树,分为大根堆和小根堆 在完全二叉树里,每一棵子数最大的值是头节点的值,就是大根堆 同理&…...
C++类型转换
C语言的转换是在变量前加类型名进行转换的,比如double pi 3.14;int a (int) pi;对于指针也是如此double* dptr πint* iptr (int*)dptr;虽然c兼容了C语言的转型方式,但是也做了很多限制,比如向上类型转换,在c中建议使用…...
Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台(2023-03-11)
注:这个是MDK6,不是MDK5 AC6,属于下一代MDK视频版: https://www.bilibili.com/video/BV16s4y157WF Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台一年一度的全球顶级嵌入式会展Embedded Wor…...
蓝桥杯刷题第九天
题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。素数就是不能再进行等分的整数。比如7,11。而 9 不是素数,因为它可以平分为 3 等份。一般认为最小的素数是2,接着是 3,5&…...
a-tree-select 基本使用,下拉框高度和宽度设置、回显时滚动条定位解决。
目录一、基本使用1. 界面效果2. 代码实现3. 问题1:下拉框占满整个屏幕4. 问题4:菜单内容过长时,下拉菜单宽度无限变宽。二、数据回显、滚动条定位1. 界面效果2. 代码实现2.1 获取默认展开节点2.1.1 代码实现2.1.2 说明2.2 设置滚动条定位2.2.…...
【Linux】之nc命令(连接与扫描指定端口、监测服务端口的使用情况)解析、详解实例、邮件告警
🍁博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 文章目录nc命令简介nc命令的安装nc命令语法格式…...
cdn简单配置
cdn配置域名接入CDN编辑CDN配置本地修改hosts文件,绕过公网解析域名接入CDN 添加CDN域名以及回源配置 编辑CDN配置 默认后端端口是80,如果测试发现无法访问,则可能是443或其它 如果域名在CDN后端有https强制跳转,后端端口一定是44…...
前端安全(自留)
目录XSS——跨站脚本常见解决CSRF ——跨站请求伪造常见解决XSS——跨站脚本 当目标站点在渲染html的过程中,遇到陌生的脚本指令执行。 攻击者通过在网站注入恶意脚本,使之在用户的浏览器上运行,从而盗取用户的信息如 cookie 等。 常见 解…...
零基础转行云计算可行吗
目前处于云年代,云计算运维工程师的工作远景还是十分广泛的。像是阿里云计算,滴滴,抖音等等互联网大厂目前都在使用云核算技能。 云计算运维工程师的薪资水平也十分可观。 运维工程师(Operations),在国内又称为运维开发工程师(Dev…...
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC &…...
孩子免费就读|私企经理自费赴美国东海岸高校访学
私企U经理无文章无课题,出国访学除了为考察市场、拓宽人脉、提升履资外,另一个主要目的是带孩子在美国接受当地免费的公立中小学教育,并把访学目标学校定位在东海岸。最终其采纳了板凳费相对较低的佐治亚大学邀请函,签证时居然全家…...
前端面试hr经常会问的问题
文章目录前言1.自我介绍2.为什么你要离职?3.工作经历4.职业规划5.优点、缺点6.还有什么要问的总结前言 这里记录了一些面试中hr或者项目负责人经常会问的一些问题,可以提前参考参考,想想该怎么回答,为之后的面试做好准备…...
C动态数组
在实际项目中,我们经常与各式各样的数据打交道。 例如:我们处理的是学生的数据。 struct student {int id; // 学号char name[20]; // 姓名int gender; // 性别int mark; // 成绩 };学生数据使用一个结构体表示,该结构体拥有4个成员。分别为…...
【STL一】STL组件(容器、迭代器、算法)
【STL一】STL组件(容器、迭代器、算法)一、STL二、STL组件(component)1、stl六大组件2、C STL的13个头文件3、stl所有头文件三、容器(container)1、序列容器(Sequence container)——顺序容器2、关联容器&a…...
Java每日一练(20230312)
目录 1. 两数之和 II ★ 2. 反转链表 ★★ 3. 二叉树的层序遍历 II ★★★ 🌟 每日一练刷题专栏 C/C 每日一练 专栏 Python 每日一练 专栏 Java 每日一练 专栏 1. 两数之和 II 给定一个已按照 非递减顺序排列 的整数数组 numbers ,请你从数…...
Linux中sudo,su与su -命令的区别
前言 su命令就是切换用户的工具,怎么理解呢?比如我们以普通用户tom登录的,但要添加用户任务,执行useradd ,tom用户没有这个权限,而这个权限恰恰由root所拥有。解决办法无法有两个,一是退出tom用…...
归并排序有多简单?一幅图教你看懂【C语言】
目录 归并排序的递归实现 代码实现 归并排序的非递归实现 代码实现 归并排序的思想很简单——分治法。简单地说,归并排序的是将序列拆分成几段子序列,将每一段子序列分别进行排序,排好之后再将有序的子序列归并(有点像合并两…...
C++-Z字扫描实现(Zigzag Scan)
Z字扫描(Zigzag Scan) 将二维矩阵压缩成行输出: int index0; for(int i0;i<rowscols-1;i){//i是第几条对角线if(i&1){//odd,向下扫描for(int jmax(0,i-cols1);j<min(i,row-1);j){res[index]mtx[j][i-j];}//}else{//偶数,向上扫描for(int jmi…...
【华为机试真题详解 Python实现】求最大数字【2023 Q1 | 100分】
文章目录 前言题目描述输入描述输出描述示例 1示例 2题目解析参考代码前言 《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。 如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议! 本文解法非最优解(即…...
面对数万亿产业规模,如何掘金工业互联网?
近年来,加速工业互联网建设的声音越来越响亮。一方面,政策利好,持续驱动。从2017年的《国务院关于深化“互联网先进制造业” 发展工业互联网的指导意见》到《工业互联网创新发展三年行动计划(2021-2023年)》࿰…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
