当前位置: 首页 > 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…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...