数据结构与算法之堆排序
目录
- 堆排序概述
- 代码实现
- 时间复杂度
堆排序概述
堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:
同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:
-
大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
-
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)
1)假设给定无序序列结构如下

2)此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整

3)找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换
4)这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。
此时,我们就将一个无需序列构造成了一个大顶堆
步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换
1)将堆顶元素9和末尾元素4进行交换,9就不用继续排序了

2)重新调整结构,使其继续构建大顶堆(9除外)

3)再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.

步骤三 后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

排序思路:
-
将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
-
将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
-
重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序
动图展示:

代码实现
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr = {4, 6, 8, 5, 9};heapSort(arr);
// [4, 6, 8, 5, 9]
// [4, 9, 8, 5, 6]
// [4, 9, 8, 5, 6]
// [9, 6, 8, 5, 4]
// [9, 6, 8, 5, 4]
// [9, 6, 8, 5, 4]
// [8, 6, 4, 5, 9]
// [8, 6, 4, 5, 9]
// [6, 5, 4, 8, 9]
// [6, 5, 4, 8, 9]
// [5, 4, 6, 8, 9]
// [5, 4, 6, 8, 9]
// [4, 5, 6, 8, 9]}//堆排序public static void heapSort(int[] arr) {//开始位置是最后一个非叶子节点(最后一个节点的父节点)int start = (arr.length - 1) / 2;//循环调整为大顶堆for (int i = start; i >= 0; i--) {maxHeap(arr, arr.length, i);}//先把数组中第0个和堆中最后一个交换位置for (int i = arr.length - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;//再把前面的处理为大顶堆maxHeap(arr, i, 0);}}//数组转大顶堆,size:调整多少(从最后一个向前减),index:调整哪一个(最后一个非叶子节点)public static void maxHeap(int[] arr, int size, int index) {//左子节点int leftNode = 2 * index + 1;//右子节点int rightNode = 2 * index + 2;//先设当前为最大节点int max = index;//和两个子节点分别对比,找出最大的节点if (leftNode < size && arr[leftNode] > arr[max]) {max = leftNode;}if (rightNode < size && arr[rightNode] > arr[max]) {max = rightNode;}//交换位置if (max != index) {int temp = arr[index];arr[index] = arr[max];arr[max] = temp;//交换位置后,可能会破坏之前排好的堆,所以之间排好的堆需要重新调整maxHeap(arr, size, max);}//打印每次排序后的结果System.out.println(Arrays.toString(arr));}
}
时间复杂度
- 最优时间复杂度:
o(nlogn) - 最坏时间复杂度:
o(nlogn) - 稳定性:不稳定
它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
在构建堆的过程中,因为我们是完全二叉树从最下层最右边的非终端结点开始构建,将它与其孩子进行比较和若有必要的互换,对于每个非终端结点来说,其实最多进行两次比较和互换操作,因此整个构建堆的时间复杂度为O(n)。
在正式排序时,第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为log2i+1),并且需要取n-1次堆顶记录,因此,重建堆的时间复杂度为O(nlogn)。
所以总体来说,堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。
空间复杂度上,它只有一个用来交换的暂存单元,也非常的不错。不过由于记录的比较与交换是跳跃式进行,因此堆排序是一种不稳定的排序方法。
相关文章:
数据结构与算法之堆排序
目录堆排序概述代码实现时间复杂度堆排序概述 堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点…...
Vue3 中的模板语法
目录前言一、什么是模板语法?二、内容渲染指令1. v-text2. {{ }} 插值表达式3. v-html三、双向绑定指令1. v-model2. v-model的修饰符四、属性绑定指令1. 动态绑定多个属性值2. 绑定class和style属性五、条件渲染指令1. v-if、v-else-if、v-else2. v-show3. v-if和v…...
Redis十大类型——Hash常见操作
Redis十大类型——Hash常见操作命令操作简列存放及获取获取健值对长度元素查找列出健值对对数字进行操作赋值hsetnx很明显咯它也是以健值对方式存在的,只不过value也就是值,在这里也变成了一组简直对。 🍊个🌰: 想必多…...
Python采集本地二手房,一键知晓上万房源信息
前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 所以今天教大家用Python来采集本地房源数据,帮助大家筛选好房。 话不多说,让我们开始愉快的旅程吧~ 更多精彩内容、资源皆可点击文章下方名片获取此处跳转 本文涉及知识点 采集基本流程 requests 发送…...
Ubuntu 18.04 出现GLIBC_2.28 not found的解决方法(亲测有效)
关于/lib/x86_64-linux-gnu/libc.so.6: version GLIBC_2.28’ not found出现报错,建议不要使用源码包去编译并升级。在下文有分享一个使用官方的Debian软件包去升级使用的方法。仅供参考! 环境 # uname -a Linux Ubuntu 5.4.0-144-generic #161~18.04.…...
Java文档搜索引擎总结
Java文档搜索引擎总结项目介绍项目使用的技术栈前端页面展示后端逻辑部分索引部分搜索模块部分Web模块部分项目介绍 Java文档搜索引擎项目是一个SSM项目,该项目的前端界面部分是由搜索页面和展示页面组成,后端部分索引模块(ScanAnalysis、in…...
Linux内核学习笔记——页表的那些事。
目录页表什么时候创建内核页表变化什么时候更新到用户页表源码分析常见问题解答问题一:页表到底是保存在内核空间中还是用户空间中?问题2:页表访问,软件是不是会频繁陷入内核?问题3:内存申请,软…...
C++,Qt分别读写xml文件
XML语法 第一行是XML文档声明,<>内的代表是元素,基本语法如以下所示。C常见的是使用tiny库读写,Qt使用自带的库读写; <?xml version"1.0" encoding"utf-8" standalone"yes" ?> <根元素>…...
WebStorm安装教程【2023年最新版图解】一文教会你安装
文章目录引言一、下载WebStorm三、WebStorm激活配置及创建项目Active Code安装完成尝试新建一个项目引言 今天发现了一个专注前端开发的软件,相比VSCode的话,这个好像也不错,为了后续做个API接口项目做准备。 对于入门JavaScript 开发的者&am…...
用户态和内核态,系统调用
特权指令:具有特殊权限的指令,比如清内存,重置时钟,分配系统资源,修改用户的访问权限 由于这类指令的权限最大,所以使用不当会导致整个系统崩溃 系统调用:是操作系统提供给应用程序的接口(供应…...
Java 包装类
Java 中有些类只能操作对象,因此 Java 的基本数据类型都有一个对应的包装类。 byte:Byteshort:Shortint:Integerlong:Longfloat:Floatdouble:Doublechar:Characterbooleanÿ…...
Raspberry Pi GPIO入门指南
如果您想使用 Raspberry Pi 进行数字输入/输出操作,那么您需要使用 GPIO(通用输入/输出)引脚。在这篇文章中,我们将为您提供 Raspberry Pi GPIO 的基础知识,包括如何访问和操作 GPIO 引脚。 0.认识GPIO 树莓派上的那…...
汇编语言程序设计(三)之汇编程序
系列文章 汇编语言程序设计(一) 汇编语言程序设计(二)之寄存器 汇编程序 经过上述课程的学习,我们可以编写一个完整的程序了。这章开始我们将开始编写完整的汇编语言程序,用编译和连接程序将它们连接成可…...
用二极管和电容过滤电源波动,实现简单的稳压 - 小水泵升压改装方案
简而言之,就是类似采样保持电路,当电源电压因为电机启动而骤降时,用二极管避免电容电压跟着降低,从而让电容上连接的低功耗芯片有一个比较稳定的供电电压。没什么特别的用处,省个LDO 吧,电压跌幅太大的时候…...
【数据结构与算法】数据结构有哪些?算法有哪些?
1. 算法与数据结构总览图 2.常用的数据结构 2.1.数组(Array) 数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。一个数组可以分解为多个数…...
使用Element-UI展示数据(动态查询)
学习内容来源:视频P4 本篇文章进度接着之前的文章进行续写 精简前后端分离项目搭建 Vue基础容器使用 目录选择组件修改表格组件修改分页组件增加后端接口前端请求数据接口页面初始化请求数据点击页码请求数据选择组件 在官方文档中选择现成的组件,放在页…...
lamda 表达式例子全集
1、List 转 map 1.1、key(Model属性) value Model Map<String, Model> modeMap List.stream().collect(Collectors.toMap(Model1::属性get方法, v -> v, (p1, p2) -> p1)); 1.2、key(Model1属性) value Model2 Map<String, Model1> model2Map List.stream…...
计算机网络第八版——第一章课后题答案(超详细)
第一章 该答案为博主在网络上整理,排版不易,希望大家多多点赞支持。后续将会持续更新(可以给博主点个关注~ 【1-01】计算机网络可以向用户提供哪些服务? 解答:这道题没有现成的标准答案,因为可以从不同的…...
嵌入式和Python(二):python初识及其基本使用规则
目录 一,python基本特点 二,python使用说明 ● 两种编程方式 ① 交互式编程 ② 脚本式编程 ● python中文编码 ● python行和缩进 ● python引号 ● python空行 ● python等待用户输入 ① 没有转换变量类型 ② 转换变量类型 ● python变…...
C语言详解双向链表的基本操作
目录 双链表的定义与接口函数 定义双链表 接口函数 详解接口函数的实现 创建新节点(BuyLTNode) 初始化双链表(ListInit) 双向链表打印(ListPrint) 双链表查找(ListFind) 双链…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
react更新页面数据,操作页面,双向数据绑定
// 路由不是组件的直接跳转use client,useEffect,useRouter,需3个结合, use client表示客户端 use client; import { Button,Card, Space,Tag,Table,message,Input } from antd; import { useEffect,useState } from react; impor…...
