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

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...