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

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...