【算法基础(四)】堆排序(二)
堆排序(二)
把数组从零开始连续的一段 = 完全二叉树 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年)》࿰…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...