Python篇——数据结构与算法(第二部分)
目录
二、排序算法(承接第一部分)
1、堆排序算法——树的基础知识补充
2、树的基本概念
3、二叉树基础知识
(1)满二叉树
(2)完全二叉树
(3)二叉树的存储方式(表示方式)
4、堆排序(大根堆、小根堆)
(1)堆排序过程
(2)构造堆
(3)挨个出数
5、堆排序——内置模块
6、堆排序应用——topk问题
二、排序算法(承接第一部分)
1、堆排序算法——树的基础知识补充
- 树是一种数据结构 比如:目录结构
- 树是一种可以递归定义的数据结构
- 树是由n个节点组成的集合
- 如果n=0,那这是一颗空树
- 如果n>0,那存在一个节点作为树的根节点,其他节点可以分为m个集合,每隔几何本身又是一棵树
2、树的基本概念
- 根节点、叶子结点(例如:B、C、H、P、Q等 不能分叉的节点)
- 树的深度(高度):最深有几层,图中为4
- 树的度(整个树,最大节点的度)、节点的度(F的度为3,分了3个叉)
- 孩子节点(子节点)、父节点(E为I的父节点、I为E的孩子节点)
- 子树

3、二叉树基础知识
- 度不超过2的树
- 每个节点最多有两个孩子节点
- 两个孩子节点被区分为左孩子节点和右孩子节点
(1)满二叉树
- 一个二叉树,如果每一个层的节点数都达到最大值,则这个二叉树就是满二叉树
(2)完全二叉树
- 叶节点只能出现在最下层和次下层,并且最下面一层的节点都集中在该层最左边的若干位置的二叉树

(3)二叉树的存储方式(表示方式)
- 链式存储
- 顺序存储(堆排序)

从图中我们需要找到两个问题:
- 父节点和左孩子节点的编号下标有什么关系?
- 0-1 1-3 2-5 3-7 4-9
- i - 2i+1
- 父节点和右孩子节点的编号下标有什么关系?
- 0-2 1-4 2-6 3-8 4-10
- i - 2i+2
4、堆排序(大根堆、小根堆)
- 堆:一种特殊的完全二叉树结构
- 大根堆:一颗完全二叉树,满足任一节点都比其他孩子节点大
- 小根堆:一颗完全二叉树,满足任一节点都比其他孩子节点小
- 复杂度O(nlogn)

(1)堆排序过程
- 建立堆(构造堆)
- 得到堆顶元素,为最大元素
- 去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整(向下调整)使堆有序
- 堆顶元素为第二大元素
- 重复步骤3,直到堆变空
Note:
如果不是取最后一个元素到堆顶,再进行向下调整,将会导致不是完全二叉树
(2)构造堆

先对最后一个非叶子节点进行调整

然后依次继续往上进行调整






(3)挨个出数
当堆构造好之后,在进行挨个出数
import random
import numpy as npdef sift(li, low, high):''':param li: 列表:param low: 堆的第一个元素 (根):param high: 堆的最后一个元素'''i = low # 此时i指向第一层j = 2 * i + 1 # 左孩子temp = li[low] # 暂存堆顶元素while j <= high: # 只要j没有超过high# 有右孩子且与左孩子对比 (j + 1 <= high )表示右孩子没有越界if j + 1 <= high and li[j + 1] > li[j]:j = j + 1 # j指向右孩子if temp < li[j]:li[i] = li[j]i = j # 往下走一层j = 2 * i + 1else: # temp更大li[i] = temp # 把temp放到某一层根部breakelse:li[i] = temp # temp不在根节点,跳出循环后,temp放到叶子结点处def head_sort(li):# 首先建堆n = len(li)# 寻找父亲节点 i-1//2 i=n-1for i in range((n - 2) // 2, -1, -1):# i 表示建堆的时候调整的部分根的下标sift(li, i, n - 1)# 建堆完成for i in range(n - 1, -1, -1):# i指向当前堆的最后一个元素li[0], li[i] = li[i], li[0] # 堆顶元素和最后一个元素调整sift(li, 0, i - 1) # 调整 (此时最后一个元素是i-1)li = [i for i in range(100)]
random.shuffle(li)
print(li)
head_sort(li)
print(li)
5、堆排序——内置模块
- Python内置模块——heapq(q:queue 优先队列)
- 常用函数
- heapify(x)(建堆——小根堆)
- heappush(heap,item)(往里面加元素)
- heappop(heap)往外弹出一个元素(最小的元素)
import heapq
import randomli = [i for i in range(100)]
random.shuffle(li)print(li)
heapq.heapify(li)
print(li)for i in range(100):print(heapq.heappop(li), end=',')
6、堆排序应用——topk问题
- 现在有n个数,设计算法得到前k大的数。(k<n)
- 解决思路:
- 排序后切片 O(nlogn)
- 冒泡、插入、选择排序O(kn)
- 堆排序 O(nlogk)
- 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
- 依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素;如果大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整。
- 遍历列表所有元素后,倒序弹出堆顶
例如:我们想到找到前5大的数字,我们先取前五个数字建立一个小根堆


发现0不能放进去,只剩下7、2、4、5

7比1大,所以把1换掉,在进行小根堆调整

以此类推,最后

import randomdef sift(li, low, high):''':param li: 列表:param low: 堆的第一个元素 (根):param high: 堆的最后一个元素'''i = low # i,j指向层j = 2 * i + 1 # 左孩子temp = li[low] # 暂存堆顶元素while j <= high: # 只要j没有超过high# 有右孩子且与左孩子对比 (j + 1 <= high )表示右孩子没有越界if j + 1 <= high and li[j + 1] < li[j]:j = j + 1 # j指向右孩子if temp > li[j]:li[i] = li[j]i = jj = 2 * i + 1else:li[i] = temp # 把temp放到某一层根部breakelse:li[i] = temp # temp不在根节点,跳出循环后,temp放到叶子结点处def topK(li, k):'''前k个元素'''heap = li[0:k]for i in range(k - 2 // 2, -1, -1):sift(heap, i, k - 1)# 1.建堆for i in range(k, len(li) - 1):if li[i] > heap[0]:heap[0] = li[i]sift(heap, 0, k - 1)# 2.遍历for i in range(k - 1, -1, -1):heap[0], heap[i] = heap[i], heap[0]sift(heap, 0, i - 1)# 3.返回前k个return heapif __name__ == '__main__':li = [i for i in range(100)]print(li)random.shuffle(li)print(li)print(topK(li, 10))
相关文章:
Python篇——数据结构与算法(第二部分)
目录 二、排序算法(承接第一部分) 1、堆排序算法——树的基础知识补充 2、树的基本概念 3、二叉树基础知识 (1)满二叉树 (2)完全二叉树 (3)二叉树的存储方式(表示方式…...
人工智能之读懂CNN卷积神经网络
通过往期文章的分享,我们了解了神经网络的结构,一般分为输入层,隐藏层,输出层 TensorFlow神经网络 那什么是卷积神经网络那,这就要我们追溯一下人类识别图像的原理 人类的视觉原理如下:从原始信号摄入开始(瞳孔摄入像素 Pixels),接着做初步处理(大脑皮层某些细胞发现…...
go手写Redis(1)之协议说明
手写Redis 参考大佬的go实现redis,自己实现一个简单版本的用于学习go以及网络编程相关 https://github.com/HDT3213/godis https://coding.imooc.com/class/576.html #慕课网课程 源码地址: https://gitee.com/haijun1998/go_redis RESP协议 Redis Ser…...
Hadoop/HbBase/Hive/HDFS/MapReduce都是什么?
目录 一图胜万言!! 解释说明 1. hadoop 2. hive 3. hbase 总结 一图胜万言!! 解释说明 1. hadoop 它是一个分布式计算分布式文件系统,前者其实就是 MapReduce,后者是 HDFS 。后者可以独立运行&…...
羽毛球中级提高班课后总结
2023.3.28第一课 🏸️四点对角线步伐练习🏸️ 1️⃣每一次接球一定要有启动步,脚跟离地; 2️⃣两边上网都是先迈右腿,加一个并步,最后一步大迈步,脚跟先落地; 3️⃣右边上网脚尖朝…...
多维时序预测 | Matlab基于最小二乘支持向量机LSSVM多维时间序列预测,LSSVM多变量时间序列预测
文章目录 效果一览文章概述部分源码参考资料效果一览 文章概述 基于最小二乘支持向量机LSSVM多维时间序列预测LSSVM多变量时间序列预测,matlab代码 评价指标包括:MAPE、MAE、RMSE和R2等,代码质量极高,...
KDZK-F水轮发电机转子测试仪
一、产品概述 KDZK-F水轮发电机转子测试仪是判断发电机转子绕组有无匝间短路的专用仪器,可以自动、手动(单向或双向)测量转子绕组的电压、电流、阻抗、功率、相位角等参数。 二、功能与特点 旋转鼠标,操作更方便。 可选择快速的…...
I2C通信协议原理和MPU6050
一、串口通讯 只能在两个设备之间进行 若要三台设备两两通信,则每个设备得需要两组窗口,为3组相互独立的窗口通讯 为解决这个问题:设计了总线通讯,有多种,I2C为其中一种 二、I2C通信 (1&#…...
3.5 RDD持久化机制
一、RDD持久化 1、不采用持久化操作 查看要操作的HDFS文件 以集群模式启动Spark Shell 按照图示进行操作,得RDD4和RDD5 查看RDD4内容,会从RDD1到RDD2到RDD3到RDD4跑一趟 显示RDD5内容,也会从RDD1到RDD2到RDD3到RDD5跑一趟 2、采用持久化…...
Nginx(四)
部署LNMP架构动态网站WordPress LNMPLinuxNginxMySQLPhp 环境 192.168.29.141centos8Nginx1.24.0192.168.29.142centos8MySQL8.0.33192.168.29.143centos8Php7.2.24 关闭firewalld systemctl stop firewalld systemctl disable firewalld 关闭selinux setenforce 0 sed -ir…...
【fps系统重构】-观察cpu、memroy、io -iostat
当您使用iostat命令监控磁盘I/O情况时,可以查看以下指标: rrqm/s:每秒发生的读请求被合并的次数。如果该指标很低,说明读请求较少或未被合并,可能会导致磁盘I/O负载过重。wrqm/s:每秒发生的写请求被合并的…...
iptables 添加,删除,查看,修改,及docker运行时修改端口
一,安装并启动防火墙 [rootlinux ~]# /etc/init.d/iptables start 当我们用iptables添加规则,保存后,这些规则以文件的形势存在磁盘上的,以centos为例,文件地址是/etc/sysconfig/iptables,我们可以通过命令的方式去…...
Liunx安装Android Studio
Liunx安装Android Studio 可参考官方文档: 安装 Android Studio 如需在 Linux 上安装 Android Studio,请按以下步骤操作: 1.将您下载的 .zip 文件解压缩到您应用的相应位置,例如 /usr/local/ 中(用于用户个人资料&am…...
8、Linux C/C++ 实现MySQL的图片插入以及图片的读取
本文结合了Linux C/C 实现MySQL的图片插入以及图片的读取,特别是数据库读写的具体流程 一、文件读取相关函数 fseek() 可以将文件指针移动到文件中的任意位置。其基本形式如下: int fseek(FILE *stream, long offset, int whence);其中,str…...
【搭建轻量级图床】本地搭建LightPicture开源图床管理系统 - 异地远程访问
文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进,功能也越来越多,而手机…...
微信小程序全局路由拦截
前言 略 微信小程序全局路由拦截方法1 目前微信小程序没有全局路由拦截。要想实现全局路由拦截,需要自己进行扩充。具体参考这里:微信小程序–路由拦截器。 实现思路: 替换Page的参数对象的onShow或onLoad方法。在替换的onShow或onLoad方…...
截图自动添加水印(macOS/windows)
文章目录 1. 截图自动加水印1.1. windows1.2. macOS 2. 对已有图像批量加水印2.1 windows2.2 macOS 1. 截图自动加水印 1.1. windows 直接看这篇文章,一键截图自动生成水印/自动签名主要就是使用一个叫 SPX 的软件 1.2. macOS 其实apple的操作系统,i…...
大学四年,我建议你这么学网络安全
在所有关注我的朋友中,大致分为两类,一类是社会人士,有的是安全老手,有的是其它工作但对安全感兴趣的朋友,另一类应该就是大学生了。 尤其随着国家的号召和知识的普及,越来越多的人开始对网络安全感兴趣&a…...
Spring Boot整合Redis缓存并使用注解
Spring Boot整合Redis缓存并使用注解 在Spring Boot应用程序中,您可以使用Spring Cache库与Redis缓存进行集成,以提高应用程序的性能和响应速度。Spring Cache库提供了一组注解,包括Cacheable、CachePut和CacheEvict,可以方便地将…...
通知可以根据切入点表达式来进行增强,也可以根据自己的注解值来进行增强
通知可以根据切入点表达式来进行增强,也可以根据自己的注解值(例如 Before、After、Around 等)来进行增强。 如果要根据切入点表达式来进行增强,需要在通知注解中使用 Pointcut 注解来引用切入点表达式。例如,在以下示…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
