算法05-堆排序
堆排序详解
堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法。它的核心思想是利用堆的性质(最大堆或最小堆)来实现排序。堆排序分为两个主要步骤:建堆和排序。
1. 什么是堆?
堆是一种特殊的完全二叉树,分为两种:
- 最大堆:每个节点的值都大于或等于其子节点的值。
- 最小堆:每个节点的值都小于或等于其子节点的值。
在堆排序中,通常使用最大堆。
2. 堆排序的步骤
步骤1:建堆
- 将待排序的数组看作一个完全二叉树。
- 从最后一个非叶子节点开始,逐步调整每个子树,使其满足最大堆的性质。
- 调整的过程称为堆化(Heapify):
- 比较当前节点与其左右子节点,找到最大值。
- 如果最大值不是当前节点,则交换它们的位置。
- 继续向下调整,直到子树满足最大堆的性质。
步骤2:排序
- 将堆顶元素(最大值)与数组的最后一个元素交换,此时最大值已经放到正确的位置。
- 排除最后一个元素,对剩余的堆重新进行堆化,使其再次满足最大堆的性质。
- 重复上述过程,直到堆中只剩下一个元素。
3. 堆排序的特点
时间复杂度
- 建堆:( O(n) )
- 排序:每次堆化需要 ( O(\log n) ),总共需要 ( n-1 ) 次堆化,因此排序的时间复杂度为 ( O(n \log n) )。
- 总时间复杂度:( O(n \log n) )
空间复杂度
- 堆排序是原地排序算法,不需要额外的存储空间,空间复杂度为 ( O(1) )。
稳定性
- 堆排序是不稳定的排序算法,因为在交换堆顶元素和最后一个元素时,可能会改变相同元素的相对顺序。
4. 堆排序的优缺点
优点
- 时间复杂度稳定,最坏情况下也是 ( O(n \log n) )。
- 不需要额外的存储空间,适合内存受限的环境。
缺点
- 不稳定排序,可能改变相同元素的相对顺序。
- 在实际应用中,由于频繁的交换操作,堆排序的常数因子较大,性能可能不如快速排序或归并排序。
5. 堆排序的应用场景
- 适合需要排序大规模数据的场景,尤其是对内存使用有严格限制的环境。
- 常用于实现优先队列。
总结
- 堆排序是一种高效的排序算法,通过构建最大堆并逐步提取最大值来实现排序。虽然它的时间复杂度较好,但由于其不稳定性和较大的常数因子,在实际应用中需要根据具体需求选择是否使用。
- 堆排序通过建堆和排序两个步骤,逐步将最大值放到数组末尾,最终实现排序。它的时间复杂度为O(nlogn),是一种高效的排序算法。
堆排序详解(结合例子和图形)
我们通过一个具体的例子和图形来讲解堆排序的过程。
例子
假设我们有一个待排序的数组:
[4, 10, 3, 5, 1]
我们的目标是将这个数组按升序排列。
步骤1:建堆
将数组看作一个完全二叉树:
4/ \10 3/ \5 1
目标:
将这个二叉树调整为最大堆(每个节点的值都大于或等于其子节点的值)。
调整过程
-
(1) 从最后一个非叶子节点开始(节点 10)。
-
(2) 比较节点 10 和其子节点 5 和 1,发现 10 已经是最大值,无需调整。
-
(3) 调整节点 4:
-
比较节点 4 和其子节点 10 和 3,发现 10 是最大值。
-
交换 4 和 10。
-
调整后的树:
10/ \4 3/ \ 5 1
-
-
(4) 继续调整节点 4:
-
比较节点 4 和其子节点 5 和 1,发现 5 是最大值。
-
交换 4 和 5。
-
调整后的树:
10/ \5 3/ \ 4 1
-
现在,树已经是一个最大堆。
步骤2:排序
目标:将堆顶元素(最大值)放到数组末尾,并逐步缩小堆的范围。
排序过程
-
(1) 将堆顶元素 10 与最后一个元素 1 交换:
[1, 5, 3, 4, 10]
树结构:
1/ \5 3/4
-
(2) 排除最后一个元素 10,对剩余部分重新堆化:
-
调整节点 1:
-
比较节点 1 和其子节点 5 和 3,发现 5 是最大值。
-
交换 1 和 5。
-
调整后的树:
5/ \1 3/ 4
-
-
继续调整节点 1:
-
比较节点 1 和其子节点 4,发现 4 是最大值。
-
交换 1 和 4。
-
调整后的树:
5/ \4 3/ 1
-
-
-
(3) 将堆顶元素 5 与最后一个元素 1 交换:
[1, 4, 3, 5, 10]
树结构:
1/ \4 3
-
(4) 排除最后一个元素 5,对剩余部分重新堆化:
-
调整节点 1:
-
比较节点 1 和其子节点 4 和 3,发现 4 是最大值。
-
交换 1 和 4。
-
调整后的树:
4/ \ 1 3
-
-
-
(5) 将堆顶元素 4 与最后一个元素 3 交换:
[3, 1, 4, 5, 10]
树结构:
3/1
-
(6) 排除最后一个元素 4,对剩余部分重新堆化:
-
调整节点 3:
-
比较节点 3 和其子节点 1,发现 3 已经是最大值。
-
无需调整。
-
-
(7) 将堆顶元素 3 与最后一个元素 1 交换:
[1, 3, 4, 5, 10]
最终结果
数组已经按升序排列:
[1, 3, 4, 5, 10]
图形总结
-
(1) 初始数组:
[4, 10, 3, 5, 1]
-
(2) 建堆后:
[10, 5, 3, 4, 1]
-
(3) 排序过程:
每次将堆顶元素放到数组末尾,并重新堆化。
-
(4) 最终结果:
[1, 3, 4, 5, 10]
示例代码
def heapify(arr, n, i):"""堆化函数:调整以 i 为根的子树,使其满足最大堆的性质。:param arr: 待排序的数组:param n: 堆的大小:param i: 当前根节点的索引"""largest = i # 初始化最大值为根节点left = 2 * i + 1 # 左子节点的索引right = 2 * i + 2 # 右子节点的索引# 如果左子节点存在且大于根节点if left < n and arr[left] > arr[largest]:largest = left# 如果右子节点存在且大于根节点if right < n and arr[right] > arr[largest]:largest = right# 如果最大值不是根节点,则交换并继续堆化if largest != i:arr[i], arr[largest] = arr[largest], arr[i] # 交换heapify(arr, n, largest) # 递归调整子树def heap_sort(arr):"""堆排序函数:param arr: 待排序的数组"""n = len(arr)# 步骤1:建堆# 从最后一个非叶子节点开始,逐步调整for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 步骤2:排序# 将堆顶元素(最大值)与数组末尾元素交换,并重新堆化for i in range(n - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0] # 将最大值放到数组末尾heapify(arr, i, 0) # 重新堆化剩余部分# 示例
arr = [4, 10, 3, 5, 1]
print("排序前:", arr)
heap_sort(arr)
print("排序后:", arr)
© 著作权归作者所有
相关文章:
算法05-堆排序
堆排序详解 堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法。它的核心思想是利用堆的性质(最大堆或最小堆)来实现排序。堆排序分为两个主要步骤:建堆和排序。 1. 什么是堆? 堆是一种特殊的完全二叉…...

Arrays工具类详解
目录 1. Arrays.toString() 方法 2. Arrays.deepToString() 方法 3. Arrays.equals(int[ ] arr1, int[ ] arr2) 方法 4. Arrays.equals(Object[] arr1, Object[] arr2) 方法 5. Arrays.deepEquals(Object[] arr1, Object[] arr2) 方法 6. Arrays.sort(int[] arr) 方法 7…...

无人机图像拼接数据的可视化与制图技术:以植被监测为例
无人机技术在生态环境监测中的应用越来越广泛,尤其是在植被监测领域。通过无人机获取的高分辨率影像数据,结合GIS技术,可以实现对植被覆盖、生长状况等的精确监测与分析。本文将通过一个实际案例,详细讲解无人机图像拼接数据的可视…...
在 debian 12 上安装 mysqlclient 报错
报错如下 Looking in indexes: https://pypi.tuna.tsinghua.edu.cn/simple Collecting mysqlclientUsing cached https://pypi.tuna.tsinghua.edu.cn/packages/61/68/810093cb579daae426794bbd9d88aa830fae296e85172d18cb0f0e5dd4bc/mysqlclient-2.2.7.tar.gz (91 kB)Installi…...
python基础入门:7.1迭代器与生成器
Python迭代器与生成器深度解析:高效处理海量数据的利器 # 大文件分块读取生成器模板 def chunked_file_reader(file_path, chunk_size1024*1024):"""分块读取大文件生成器"""with open(file_path, r, encodingutf-8) as f:while Tru…...
Docker 容器 Elasticsearch 启动失败完整排查记录
背景 在服务器上运行 Docker 容器 es3,但 Elasticsearch 无法正常启动,运行 docker ps -a 发现 es3 处于 Exited (1) 状态,即进程异常退出。 本次排查从错误日志、容器挂载、权限问题、SELinux 影响、内核参数等多个方面入手,最…...

达梦数据使用笔记
相关文档: 达梦官网 达梦技术文档 1.安装完成后在开始菜单中搜索DM 目录:C:\ProgramData\Microsoft\Windows\Start Menu\Programs\达梦数据库 下有所有相关信息 2.数据迁移 https://eco.dameng.com/document/dm/zh-cn/start/mysql_dm.html https:…...
操作系统中的任务调度算法
一、引言 在操作系统中,任务调度算法是核心组件之一,它负责合理分配有限的 CPU 资源,以确保系统的高效运行和良好的用户体验。任务调度的目标是实现公平性、最小化等待时间、提高系统吞吐量,并最大化 CPU 的利用率。不同的任务调…...
Linux 虚拟服务器(LVS)技术详解
一、LVS 概述 Linux 虚拟服务器(Linux Virtual Server,简称 LVS)是由章文嵩博士开发的一种开源的服务器集群技术,它工作在 Linux 内核空间,为构建高可用、可扩展的网络服务提供了一种高效的解决方案。LVS 可以将多个真…...

AIoT时代来临,物联网技术如何颠覆未来生活?
在这个万物互联的时代,“物联网”(IoT)正以前所未有的速度改变我们的生活,而“AIoT”则是在物联网基础上融入人工智能技术,赋予设备更高的智能和自主决策能力。随着5G、边缘计算和云技术的不断发展,物联网正…...
C++17 新特性解析
C++17 是 C++ 标准的一个重要更新,它在 C++11/14 的基础上引入了许多新特性,进一步简化了代码编写、提升了性能和类型安全性。以下是 C++17 的主要特性分类介绍: 一、语言核心改进 1. 结构化绑定(Structured Bindings) 允许将元组、结构体或数组的成员直接解包到变量中。…...
嵌入式软件C语言面试常见问题及答案解析(四)
嵌入式软件C语言面试常见问题及答案解析(四) 原本打算将链表相关的面试题整合到一个文档中,奈何写着写着就发现题目比较多,题型也比较丰富,所以导致上一篇已经足够长了,再长也就有点不礼貌了。 所以在这儿继续来总结分享那个面试中遇到的题目,文中的问题和提供的答案或者…...
在 C# 中,处理 Excel 和 PDF 文件的库有很多。以下是一些比较常用的选择
读取 Excel 文件的库 NPOI 用途:可以读取和写入 .xls 和 .xlsx 文件。特点:无需安装 Microsoft Office,支持简单的 Excel 操作,如格式化、公式、图表等。 EPPlus 用途:主要用于 .xlsx 格式(Excel 2007 及以…...

绩效归因概述
绩效归因概述 1. 分类2. 基于净值的归因方法2.1 发展背景2.2 择时选股模型 T-M模型2.3 择时选股模型 H-M模型2.4 择时选股模型 C-L模型2.5 风格配置模型-Sharpe2.6 多因子模型 Fama-French32.7 多因子模型 Carhart42.8 多因子模型 Fama-French5 3. 基于持仓的归因方法3.1 发展背…...
Spring Boot 中加载多个 YAML 配置文件
在 Spring Boot 中加载多个 YAML 配置文件是一个常见的需求,通常用于将配置信息分离到多个文件中以便于管理和维护。Spring Boot 提供了灵活的方式来加载多个 YAML 配置文件。 以下是一些方法和步骤,用于在 Spring Boot 应用中加载多个 YAML 配置文件&a…...
厚植创新实力、聚焦生物科技:柏强制药的责任与机遇
在当今快速发展的医药行业中,创新已成为企业竞争的核心动力。贵州柏强制药作为医药领域的佼佼者,正以科技创新为引领,聚焦生物科技领域,不断突破,不仅为人民的健康事业贡献力量,更在激烈的市场竞争中抓住了…...
Linux中getifaddrs函数
文章目录 **函数原型****参数****返回值****释放资源****`struct ifaddrs` 结构****示例代码****输出示例****相关函数****总结**getifaddrs 是 Linux(以及其他 Unix-like 系统)中用于获取本机网络接口信息的系统调用。它提供了一种简单的方法来获取所有网络接口的地址信息,…...

【HarmonyOS Next 自定义可拖拽image】
效果图: 代码: import display from "ohos.display" import { AppUtil } from "pura/harmony-utils"/*** 自定义可拖拽图标组件*/ Component export default struct DraggableImage {imageResource?: ResourceimageHeight: numbe…...
解决No module named ‘llama_index.llms.huggingface‘
执行下面的脚本,报错No module named llama_index.llms.huggingface’执行下面的脚本,报错No module named llama_index.llms.huggingface’执行下面的脚本,报错No module named llama_index.llms.huggingface’执行下面的脚本,报…...

SearchBar组件的功能与用法
文章目录 1. 概念介绍2. 使用方法3. 代码与效果3.1 示例代码3.2 运行效果 4. 内容总结 我们在上一章回中介绍了"Material3中的IconButton"相关的内容,本章回中将介绍SearchBar组件.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 我们在本…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...