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

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

【HTTP三个基础问题】

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

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...