数据结构算法--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堆排序
堆排序过程: >建立堆(大根堆) >得到堆顶元素,为最大元素 >去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整使堆重新有序 >堆顶元素为第二大元素 >重复步骤3,直到堆变空 此时是建立堆后的大根堆模型 将…...
C++学习系列之DLL动态库使用
C学习系列之DLL动态库使用 啰嗦动态库的创建动态库的调用函数生成1.需要头文件函数定义(头文件)2.需要函数定义(函数文件)3.动态库中的头文件4.动态库中的主文件5.运行查看是否存在C#的调用的入口点6.C#调用 总结 啰嗦 项目需要&…...
Java实现钉钉企业内部应用机器和自定义机器人发送消息
前言 公司让写一个服务监控的功能,当监测到服务停止时,向钉钉群里推送报警信息。之前大概看到钉钉的开放平台的API文档,好像能群发消息的只有机器人。 钉钉开放平台目前提供三种机器人: 企业内部应用机器人 群模板机器人 自定义机器人 本来向用自己比较熟悉的自定义机器人…...
基于QT4的GPX文件编辑器开发
GPX文件是记录地理点的文件,本质是一种xml文件。GPX文件目前没有很好的编辑器,因此作者决定开发一款无需安装的绿色编辑器。 在QT4开发中,XML可以用DOM来实现,但其逻辑并不是很清晰。使用模型视图反而会更加可读。因此在开发中,使用model-view模式来实现数据读写。 1 需…...
树结构使用实例---实现数组和树结构的转换
文章目录 一、为什么要用树结构?二、使用步骤 1.引入相关json2.树结构的转换总结 一、为什么要用树结构? 本文将讲述一个实例,构造一棵树来实现数组和tree的转换,这在前端树结构中是经常遇到的 后端返回树结构方便管理ÿ…...
论文阅读_条件控制_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重磅升级,全面增强数据入湖、调度和治理能力
简介: 阿里云全链路数据湖开发治理解决方案能力持续升级,发布2.0版本。解决方案包含开源大数据平台E-MapReduce(EMR) , 一站式大数据数据开发治理平台DataWorks ,数据湖构建DLF,对象存储OSS等核心产品。支持EMR新版数据…...
【算法题】2769. 找出最大的可达成数字
题目: 给你两个整数 num 和 t 。 如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等,则称其为 可达成数字 : 每次操作将 x 的值增加或减少 1 ,同时可以选择将 num 的值增加或减少 1 。 返回所有可达成数字中的…...
023:vue中解决el-date-picker更改样式不生效问题
第023个 查看专栏目录: VUE ------ element UI 本文章目录 修改后的效果示例源代码(共52行)核心内容步骤:(1)更改样式(2)添加参数 专栏目标 在vue项目开发中,我们打算保持颜色的一致…...
爬虫借助代理会让网速快点吗?
亲爱的程序员朋友们,你曾经遇到过爬虫网速慢的情况吗?别着急!今天我将和你一起探讨一下使用代理是否可以加速爬虫,让我们一起进入这个轻松又专业的知识分享。 一、原因和机制的解析 1.IP限制 某些网站为了保护资源和防止爬虫行…...
探索智能文字识别:技术、应用与发展前景
探索智能文字识别:技术、应用与发展前景 前言一张图全览大赛作品解读随心记你不对我对小结 智能文字识别体系化解读图像预处理文字定位和分割文字区域识别图像校正字体识别和匹配结果后处理小结 如何应对复杂场景下挑战复杂场景应对方法小结 人才时代对人才要求合合…...
STL——list用法
一、list介绍 1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 2、list就是一个带头双向循环链表,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: 10、mv指令 11、cat指令 12、more指令 13、less…...
深入浅出Pytorch函数——torch.nn.init.normal_
分类目录:《深入浅出Pytorch函数》总目录 相关文章: 深入浅出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是命令式编程,当渲染在页面的数据发生一点点变化,需要整个重新渲染一编。vue.js渐进式框架有个虚拟DOM的概念,运用diff算法,比较新旧数据,相同的数据不变不重渲染,不同的部分新数据…...
Sui第四轮资助:16个团队瓜分
近日,Sui基金会公布了第四轮开发者资助名单,受助项目均是集中在DeFi、支付、基础设施、游戏、预言机等领域的Sui生态项目,他们是从2023年7月1日之前提交的申请中选出的。在此时间之后提交的任何项目目前正在审查中。 在前三轮资助中累积发放…...
ATC模型转换环境问题案例
ATC(Ascend Tensor Compiler)是异构计算架构CANN体系下的模型转换工具:它可以将开源框架的网络模型(如TensorFlow等)以及Ascend IR定义的单算子描述文件转换为昇腾AI处理器支持的离线模型;模型转换过程中&a…...
dart其他语法
dart其他语法 类型相关 空安全 不能将一个普通类型对象赋值为 null 避免 为空 报错:对 null 的使用语法进行限制(str ! null)对空安全的允诺 late 延迟初始化的时机 ! 在此时该可用变量一定不为空 void main() {String name zh…...
C++11并发与多线程笔记(7) 单例设计模式共享数据分析、解决,call_once
C11并发与多线程笔记(7) 单例设计模式共享数据分析、解决,call_once 1.设计模式2.单例设计模式:3.单例设计模式共享数据分析、解决4.std::call_once(): 1.设计模式 程序灵活,维护起来可能方便,…...
FANUC机器人加减速倍率指令ACC的使用方法说明
FANUC机器人加减速倍率指令ACC的使用方法说明 单位有一台FANUC机器人(型号:M-900iB 360kg),偶尔会在启动的瞬间会报SRVO-050碰撞检测报警,而事实上机器人并没有开始移动或和其他工件产生碰撞,一直查了很长时间,也没有查到具体的原因,也尝试过重新进行负载推算,但是偶尔…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
