当前位置: 首页 > 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碰撞检测报警,而事实上机器人并没有开始移动或和其他工件产生碰撞,一直查了很长时间,也没有查到具体的原因,也尝试过重新进行负载推算,但是偶尔…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...