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

算法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-堆排序

堆排序详解 堆排序&#xff08;Heap Sort&#xff09;是一种基于二叉堆数据结构的排序算法。它的核心思想是利用堆的性质&#xff08;最大堆或最小堆&#xff09;来实现排序。堆排序分为两个主要步骤&#xff1a;建堆和排序。 1. 什么是堆&#xff1f; 堆是一种特殊的完全二叉…...

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…...

无人机图像拼接数据的可视化与制图技术:以植被监测为例

无人机技术在生态环境监测中的应用越来越广泛&#xff0c;尤其是在植被监测领域。通过无人机获取的高分辨率影像数据&#xff0c;结合GIS技术&#xff0c;可以实现对植被覆盖、生长状况等的精确监测与分析。本文将通过一个实际案例&#xff0c;详细讲解无人机图像拼接数据的可视…...

在 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迭代器与生成器深度解析&#xff1a;高效处理海量数据的利器 # 大文件分块读取生成器模板 def chunked_file_reader(file_path, chunk_size1024*1024):"""分块读取大文件生成器"""with open(file_path, r, encodingutf-8) as f:while Tru…...

Docker 容器 Elasticsearch 启动失败完整排查记录

背景 在服务器上运行 Docker 容器 es3&#xff0c;但 Elasticsearch 无法正常启动&#xff0c;运行 docker ps -a 发现 es3 处于 Exited (1) 状态&#xff0c;即进程异常退出。 本次排查从错误日志、容器挂载、权限问题、SELinux 影响、内核参数等多个方面入手&#xff0c;最…...

达梦数据使用笔记

相关文档&#xff1a; 达梦官网 达梦技术文档 1.安装完成后在开始菜单中搜索DM 目录&#xff1a;C:\ProgramData\Microsoft\Windows\Start Menu\Programs\达梦数据库 下有所有相关信息 2.数据迁移 https://eco.dameng.com/document/dm/zh-cn/start/mysql_dm.html https:…...

操作系统中的任务调度算法

一、引言 在操作系统中&#xff0c;任务调度算法是核心组件之一&#xff0c;它负责合理分配有限的 CPU 资源&#xff0c;以确保系统的高效运行和良好的用户体验。任务调度的目标是实现公平性、最小化等待时间、提高系统吞吐量&#xff0c;并最大化 CPU 的利用率。不同的任务调…...

Linux 虚拟服务器(LVS)技术详解

一、LVS 概述 Linux 虚拟服务器&#xff08;Linux Virtual Server&#xff0c;简称 LVS&#xff09;是由章文嵩博士开发的一种开源的服务器集群技术&#xff0c;它工作在 Linux 内核空间&#xff0c;为构建高可用、可扩展的网络服务提供了一种高效的解决方案。LVS 可以将多个真…...

AIoT时代来临,物联网技术如何颠覆未来生活?

在这个万物互联的时代&#xff0c;“物联网”&#xff08;IoT&#xff09;正以前所未有的速度改变我们的生活&#xff0c;而“AIoT”则是在物联网基础上融入人工智能技术&#xff0c;赋予设备更高的智能和自主决策能力。随着5G、边缘计算和云技术的不断发展&#xff0c;物联网正…...

C++17 新特性解析

C++17 是 C++ 标准的一个重要更新,它在 C++11/14 的基础上引入了许多新特性,进一步简化了代码编写、提升了性能和类型安全性。以下是 C++17 的主要特性分类介绍: 一、语言核心改进 1. 结构化绑定(Structured Bindings) 允许将元组、结构体或数组的成员直接解包到变量中。…...

嵌入式软件C语言面试常见问题及答案解析(四)

嵌入式软件C语言面试常见问题及答案解析(四) 原本打算将链表相关的面试题整合到一个文档中,奈何写着写着就发现题目比较多,题型也比较丰富,所以导致上一篇已经足够长了,再长也就有点不礼貌了。 所以在这儿继续来总结分享那个面试中遇到的题目,文中的问题和提供的答案或者…...

在 C# 中,处理 Excel 和 PDF 文件的库有很多。以下是一些比较常用的选择

读取 Excel 文件的库 NPOI 用途&#xff1a;可以读取和写入 .xls 和 .xlsx 文件。特点&#xff1a;无需安装 Microsoft Office&#xff0c;支持简单的 Excel 操作&#xff0c;如格式化、公式、图表等。 EPPlus 用途&#xff1a;主要用于 .xlsx 格式&#xff08;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 配置文件是一个常见的需求&#xff0c;通常用于将配置信息分离到多个文件中以便于管理和维护。Spring Boot 提供了灵活的方式来加载多个 YAML 配置文件。 以下是一些方法和步骤&#xff0c;用于在 Spring Boot 应用中加载多个 YAML 配置文件&a…...

厚植创新实力、聚焦生物科技:柏强制药的责任与机遇

在当今快速发展的医药行业中&#xff0c;创新已成为企业竞争的核心动力。贵州柏强制药作为医药领域的佼佼者&#xff0c;正以科技创新为引领&#xff0c;聚焦生物科技领域&#xff0c;不断突破&#xff0c;不仅为人民的健康事业贡献力量&#xff0c;更在激烈的市场竞争中抓住了…...

Linux中getifaddrs函数

文章目录 **函数原型****参数****返回值****释放资源****`struct ifaddrs` 结构****示例代码****输出示例****相关函数****总结**getifaddrs 是 Linux(以及其他 Unix-like 系统)中用于获取本机网络接口信息的系统调用。它提供了一种简单的方法来获取所有网络接口的地址信息,…...

【HarmonyOS Next 自定义可拖拽image】

效果图&#xff1a; 代码&#xff1a; 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‘

执行下面的脚本&#xff0c;报错No module named llama_index.llms.huggingface’执行下面的脚本&#xff0c;报错No module named llama_index.llms.huggingface’执行下面的脚本&#xff0c;报错No module named llama_index.llms.huggingface’执行下面的脚本&#xff0c;报…...

SearchBar组件的功能与用法

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

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

深入理解 React 样式方案

React 的样式方案较多,在应用开发初期,开发者需要根据项目业务具体情况选择对应样式方案。React 样式方案主要有: 1. 内联样式 2. module css 3. css in js 4. tailwind css 这些方案中,均有各自的优势和缺点。 1. 方案优劣势 1. 内联样式: 简单直观,适合动态样式和…...

鸿蒙Navigation路由导航-基本使用介绍

1. Navigation介绍 Navigation组件是路由导航的根视图容器&#xff0c;一般作为Page页面的根容器使用&#xff0c;其内部默认包含了标题栏、内容区和工具栏&#xff0c;其中内容区默认首页显示导航内容&#xff08;Navigation的子组件&#xff09;或非首页显示&#xff08;Nav…...