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

【算法基础(四)】堆排序(二)

堆排序(二)

把数组从零开始连续的一段 = 完全二叉树 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());}
}

相关文章:

【算法基础(四)】堆排序(二)

堆排序&#xff08;二&#xff09; 把数组从零开始连续的一段 完全二叉树 size i 左 son 2*11 i 右 son 2*12 父 (i-1) / 2 堆是完全二叉树&#xff0c;分为大根堆和小根堆 在完全二叉树里&#xff0c;每一棵子数最大的值是头节点的值&#xff0c;就是大根堆 同理&…...

C++类型转换

C语言的转换是在变量前加类型名进行转换的&#xff0c;比如double pi 3.14;int a (int) pi;对于指针也是如此double* dptr &pi;int* iptr (int*)dptr;虽然c兼容了C语言的转型方式&#xff0c;但是也做了很多限制&#xff0c;比如向上类型转换&#xff0c;在c中建议使用…...

Keil MDK6要来了,将嵌入式软件开发水平带到新高度,支持跨平台(2023-03-11)

注&#xff1a;这个是MDK6&#xff0c;不是MDK5 AC6&#xff0c;属于下一代MDK视频版&#xff1a; https://www.bilibili.com/video/BV16s4y157WF Keil MDK6要来了&#xff0c;将嵌入式软件开发水平带到新高度&#xff0c;支持跨平台一年一度的全球顶级嵌入式会展Embedded Wor…...

蓝桥杯刷题第九天

题目描述本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。素数就是不能再进行等分的整数。比如7&#xff0c;11。而 9 不是素数&#xff0c;因为它可以平分为 3 等份。一般认为最小的素数是2&#xff0c;接着是 3&#xff0c;5&…...

a-tree-select 基本使用,下拉框高度和宽度设置、回显时滚动条定位解决。

目录一、基本使用1. 界面效果2. 代码实现3. 问题1&#xff1a;下拉框占满整个屏幕4. 问题4&#xff1a;菜单内容过长时&#xff0c;下拉菜单宽度无限变宽。二、数据回显、滚动条定位1. 界面效果2. 代码实现2.1 获取默认展开节点2.1.1 代码实现2.1.2 说明2.2 设置滚动条定位2.2.…...

【Linux】之nc命令(连接与扫描指定端口、监测服务端口的使用情况)解析、详解实例、邮件告警

&#x1f341;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; 文章目录nc命令简介nc命令的安装nc命令语法格式…...

cdn简单配置

cdn配置域名接入CDN编辑CDN配置本地修改hosts文件&#xff0c;绕过公网解析域名接入CDN 添加CDN域名以及回源配置 编辑CDN配置 默认后端端口是80&#xff0c;如果测试发现无法访问&#xff0c;则可能是443或其它 如果域名在CDN后端有https强制跳转&#xff0c;后端端口一定是44…...

前端安全(自留)

目录XSS——跨站脚本常见解决CSRF ——跨站请求伪造常见解决XSS——跨站脚本 当目标站点在渲染html的过程中&#xff0c;遇到陌生的脚本指令执行。 攻击者通过在网站注入恶意脚本&#xff0c;使之在用户的浏览器上运行&#xff0c;从而盗取用户的信息如 cookie 等。 常见 解…...

零基础转行云计算可行吗

目前处于云年代&#xff0c;云计算运维工程师的工作远景还是十分广泛的。像是阿里云计算&#xff0c;滴滴&#xff0c;抖音等等互联网大厂目前都在使用云核算技能。 云计算运维工程师的薪资水平也十分可观。 运维工程师(Operations)&#xff0c;在国内又称为运维开发工程师(Dev…...

【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)

目录 写在前面&#xff1a; 题目&#xff1a;92. 递归实现指数型枚举 - AcWing题库 读题&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 数据范围&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; 代码&#xff1a; AC &…...

孩子免费就读|私企经理自费赴美国东海岸高校访学

私企U经理无文章无课题&#xff0c;出国访学除了为考察市场、拓宽人脉、提升履资外&#xff0c;另一个主要目的是带孩子在美国接受当地免费的公立中小学教育&#xff0c;并把访学目标学校定位在东海岸。最终其采纳了板凳费相对较低的佐治亚大学邀请函&#xff0c;签证时居然全家…...

前端面试hr经常会问的问题

文章目录前言1.自我介绍2.为什么你要离职&#xff1f;3.工作经历4.职业规划5.优点、缺点6.还有什么要问的总结前言 这里记录了一些面试中hr或者项目负责人经常会问的一些问题&#xff0c;可以提前参考参考&#xff0c;想想该怎么回答&#xff0c;为之后的面试做好准备&#xf…...

C动态数组

在实际项目中&#xff0c;我们经常与各式各样的数据打交道。 例如&#xff1a;我们处理的是学生的数据。 struct student {int id; // 学号char name[20]; // 姓名int gender; // 性别int mark; // 成绩 };学生数据使用一个结构体表示&#xff0c;该结构体拥有4个成员。分别为…...

【STL一】STL组件(容器、迭代器、算法)

【STL一】STL组件&#xff08;容器、迭代器、算法&#xff09;一、STL二、STL组件&#xff08;component&#xff09;1、stl六大组件2、C STL的13个头文件3、stl所有头文件三、容器&#xff08;container)1、序列容器&#xff08;Sequence container)——顺序容器2、关联容器&a…...

Java每日一练(20230312)

目录 1. 两数之和 II ★ 2. 反转链表 ★★ 3. 二叉树的层序遍历 II ★★★ &#x1f31f; 每日一练刷题专栏 C/C 每日一练 ​专栏 Python 每日一练 专栏 Java 每日一练 专栏 1. 两数之和 II 给定一个已按照 非递减顺序排列 的整数数组 numbers &#xff0c;请你从数…...

Linux中sudo,su与su -命令的区别

前言 su命令就是切换用户的工具&#xff0c;怎么理解呢&#xff1f;比如我们以普通用户tom登录的&#xff0c;但要添加用户任务&#xff0c;执行useradd &#xff0c;tom用户没有这个权限&#xff0c;而这个权限恰恰由root所拥有。解决办法无法有两个&#xff0c;一是退出tom用…...

归并排序有多简单?一幅图教你看懂【C语言】

目录 归并排序的递归实现 代码实现 归并排序的非递归实现 代码实现 归并排序的思想很简单——分治法。简单地说&#xff0c;归并排序的是将序列拆分成几段子序列&#xff0c;将每一段子序列分别进行排序&#xff0c;排好之后再将有序的子序列归并&#xff08;有点像合并两…...

C++-Z字扫描实现(Zigzag Scan)

Z字扫描(Zigzag Scan) 将二维矩阵压缩成行输出&#xff1a; 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{//偶数&#xff0c;向上扫描for(int jmi…...

【华为机试真题详解 Python实现】求最大数字【2023 Q1 | 100分】

文章目录 前言题目描述输入描述输出描述示例 1示例 2题目解析参考代码前言 《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。 如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议! 本文解法非最优解(即…...

面对数万亿产业规模,如何掘金工业互联网?

近年来&#xff0c;加速工业互联网建设的声音越来越响亮。一方面&#xff0c;政策利好&#xff0c;持续驱动。从2017年的《国务院关于深化“互联网先进制造业” 发展工业互联网的指导意见》到《工业互联网创新发展三年行动计划&#xff08;2021-2023年&#xff09;》&#xff0…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

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智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&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 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...