当前位置: 首页 > 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. 概念介绍 我们在本…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...