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

数据结构算法--4堆排序

堆排序过程:

>建立堆(大根堆)

>得到堆顶元素,为最大元素

>去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整使堆重新有序

>堆顶元素为第二大元素

>重复步骤3,直到堆变空

 此时是建立堆后的大根堆模型

将9拿下来,为了节约内存,提高利用率,可以将9放到3(最后一个元素),然后3放到堆顶,再此经过调整,3放到合适的位置并且除了9的最大元素又被调到堆顶。

每次经过调整,整个堆的最后几个元素不断形成有序区,即,大根堆在不断变小

首先我们要调整一个无序列表等成为一个大根堆(先将列表看成一个堆)

 我们要从最末尾开始调整,才能保证大元素一步步被调上去

 

 我们可以看出是从最后一个元素的根节点开始调整,即5,9,1...

列表长为n=len(li),所以5的下标为(n-2)//2

我们可以先写调整部分的代码:

def sift(li,low,high):   # 堆的第一个元素和最后一个元素i=lowj=2*i+1       # j刚开始是左孩子tmp=li[low]   # 把堆顶存起来while j<=high: # 只要j位置有数,没有越界if j+1<=high and li[j+1]>li[j]:   # 保证右孩子不越界,因为最右侧列表是有序区,不是堆j=j+1    # j指向右孩子          # 与左右孩子对比前,先左右孩子比较if li[j]>tmp:li[i]=li[j]i=jj=2*i+1else:li[i]=tmpbreakelse:li[i]=tmp  # 到最后了,通过计算左孩子已经超出high了

堆排序的代码:

def heap_sort(li):n=len(li)for i in range((n-2)//2,-1,-1):   # 倒着走,一直往左遍历,第一个元素的前一个元素就是-1下标# i表示建堆时调整的部分的根的下标sift(li,i,n-1)   # 避免麻烦直接选最后,high作用只有一个就是确定别越界print(li)# 建堆完成了for i in range(n-1,-1,-1):     # 一直确定堆最后元素# i一直指向当前堆的最后一个元素li[0],li[i]=li[i],li[0]sift(li,0,i-1)

实验代码:

li=[i for i in range(12)]
random.shuffle(li)
print(li)heap_sort(li)
print(li)

可以看出堆排序时间复杂度为O(nlogn)

当然python内部也有堆的内置模块

import heapq
import randomli=list(range(12))
random.shuffle(li)print(li)heapq.heapify(li)   # 默认建立小根堆
n=len(li)
for i in range(n):print(heapq.heappop(li))   # 每次弹出一个元素

相关文章:

数据结构算法--4堆排序

堆排序过程: >建立堆(大根堆) >得到堆顶元素&#xff0c;为最大元素 >去掉堆顶&#xff0c;将堆最后一个元素放到堆顶&#xff0c;此时可通过一次调整使堆重新有序 >堆顶元素为第二大元素 >重复步骤3&#xff0c;直到堆变空 此时是建立堆后的大根堆模型 将…...

C++学习系列之DLL动态库使用

C学习系列之DLL动态库使用 啰嗦动态库的创建动态库的调用函数生成1.需要头文件函数定义&#xff08;头文件&#xff09;2.需要函数定义&#xff08;函数文件&#xff09;3.动态库中的头文件4.动态库中的主文件5.运行查看是否存在C#的调用的入口点6.C#调用 总结 啰嗦 项目需要&…...

Java实现钉钉企业内部应用机器和自定义机器人发送消息

前言 公司让写一个服务监控的功能,当监测到服务停止时,向钉钉群里推送报警信息。之前大概看到钉钉的开放平台的API文档,好像能群发消息的只有机器人。 钉钉开放平台目前提供三种机器人: 企业内部应用机器人 群模板机器人 自定义机器人 本来向用自己比较熟悉的自定义机器人…...

基于QT4的GPX文件编辑器开发

GPX文件是记录地理点的文件,本质是一种xml文件。GPX文件目前没有很好的编辑器,因此作者决定开发一款无需安装的绿色编辑器。 在QT4开发中,XML可以用DOM来实现,但其逻辑并不是很清晰。使用模型视图反而会更加可读。因此在开发中,使用model-view模式来实现数据读写。 1 需…...

树结构使用实例---实现数组和树结构的转换

文章目录 一、为什么要用树结构&#xff1f;二、使用步骤 1.引入相关json2.树结构的转换总结 一、为什么要用树结构&#xff1f; 本文将讲述一个实例&#xff0c;构造一棵树来实现数组和tree的转换&#xff0c;这在前端树结构中是经常遇到的 后端返回树结构方便管理&#xff…...

论文阅读_条件控制_ControlNet

name_en: Adding Conditional Control to Text-to-Image Diffusion Models name_ch: 向文本到图像的扩散模型添加条件控制 paper_addr: http://arxiv.org/abs/2302.05543 date_read: 2023-08-17 date_publish: 2023-02-10 tags: [‘图形图像’,‘大模型’,‘多模态’] author: …...

全链路数据湖开发治理解决方案2.0重磅升级,全面增强数据入湖、调度和治理能力

简介&#xff1a; 阿里云全链路数据湖开发治理解决方案能力持续升级&#xff0c;发布2.0版本。解决方案包含开源大数据平台E-MapReduce(EMR) &#xff0c; 一站式大数据数据开发治理平台DataWorks &#xff0c;数据湖构建DLF&#xff0c;对象存储OSS等核心产品。支持EMR新版数据…...

【算法题】2769. 找出最大的可达成数字

题目&#xff1a; 给你两个整数 num 和 t 。 如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等&#xff0c;则称其为 可达成数字 &#xff1a; 每次操作将 x 的值增加或减少 1 &#xff0c;同时可以选择将 num 的值增加或减少 1 。 返回所有可达成数字中的…...

023:vue中解决el-date-picker更改样式不生效问题

第023个 查看专栏目录: VUE ------ element UI 本文章目录 修改后的效果示例源代码&#xff08;共52行&#xff09;核心内容步骤&#xff1a;&#xff08;1&#xff09;更改样式&#xff08;2&#xff09;添加参数 专栏目标 在vue项目开发中&#xff0c;我们打算保持颜色的一致…...

爬虫借助代理会让网速快点吗?

亲爱的程序员朋友们&#xff0c;你曾经遇到过爬虫网速慢的情况吗&#xff1f;别着急&#xff01;今天我将和你一起探讨一下使用代理是否可以加速爬虫&#xff0c;让我们一起进入这个轻松又专业的知识分享。 一、原因和机制的解析 1.IP限制 某些网站为了保护资源和防止爬虫行…...

探索智能文字识别:技术、应用与发展前景

探索智能文字识别&#xff1a;技术、应用与发展前景 前言一张图全览大赛作品解读随心记你不对我对小结 智能文字识别体系化解读图像预处理文字定位和分割文字区域识别图像校正字体识别和匹配结果后处理小结 如何应对复杂场景下挑战复杂场景应对方法小结 人才时代对人才要求合合…...

STL——list用法

一、list介绍 1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。 2、list就是一个带头双向循环链表&#xff0c;list通常在任意位置进行插入、移除元素的执行效率更好。 3、list最大的缺陷是不支持任意位置的随机访问…...

Linux的基础指令

目录 1、ls指令 .和..意义 2、pwd指令 3、cd指令 ①cd ~ ②cd - 关于cd ..的用法 绝对路径和相对路径 4、touch指令 5、mkdir指令 tree指令 6、rmdir指令 7、rm指令 * 8、man指令 9、cp指令 nano&#xff1a; 10、mv指令 11、cat指令 12、more指令 13、less…...

深入浅出Pytorch函数——torch.nn.init.normal_

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 相关文章&#xff1a; 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...

Vue.js知识点学习的一点笔记

一、虚拟DOM 1、原生JS是命令式编程&#xff0c;当渲染在页面的数据发生一点点变化&#xff0c;需要整个重新渲染一编。vue.js渐进式框架有个虚拟DOM的概念&#xff0c;运用diff算法&#xff0c;比较新旧数据&#xff0c;相同的数据不变不重渲染&#xff0c;不同的部分新数据…...

Sui第四轮资助:16个团队瓜分

近日&#xff0c;Sui基金会公布了第四轮开发者资助名单&#xff0c;受助项目均是集中在DeFi、支付、基础设施、游戏、预言机等领域的Sui生态项目&#xff0c;他们是从2023年7月1日之前提交的申请中选出的。在此时间之后提交的任何项目目前正在审查中。 在前三轮资助中累积发放…...

ATC模型转换环境问题案例

ATC&#xff08;Ascend Tensor Compiler&#xff09;是异构计算架构CANN体系下的模型转换工具&#xff1a;它可以将开源框架的网络模型&#xff08;如TensorFlow等&#xff09;以及Ascend IR定义的单算子描述文件转换为昇腾AI处理器支持的离线模型&#xff1b;模型转换过程中&a…...

dart其他语法

dart其他语法 类型相关 空安全 不能将一个普通类型对象赋值为 null 避免 为空 报错&#xff1a;对 null 的使用语法进行限制&#xff08;str &#xff01; null&#xff09;对空安全的允诺 late 延迟初始化的时机 ! 在此时该可用变量一定不为空 void main() {String name zh…...

C++11并发与多线程笔记(7) 单例设计模式共享数据分析、解决,call_once

C11并发与多线程笔记&#xff08;7&#xff09; 单例设计模式共享数据分析、解决&#xff0c;call_once 1.设计模式2.单例设计模式&#xff1a;3.单例设计模式共享数据分析、解决4.std::call_once()&#xff1a; 1.设计模式 程序灵活&#xff0c;维护起来可能方便&#xff0c;…...

FANUC机器人加减速倍率指令ACC的使用方法说明

FANUC机器人加减速倍率指令ACC的使用方法说明 单位有一台FANUC机器人(型号:M-900iB 360kg),偶尔会在启动的瞬间会报SRVO-050碰撞检测报警,而事实上机器人并没有开始移动或和其他工件产生碰撞,一直查了很长时间,也没有查到具体的原因,也尝试过重新进行负载推算,但是偶尔…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...