算法——python实现堆排序

文章目录

      • 堆排序
        • 二叉树
        • 堆排序的过程:
        • 代码实现
        • python中的heapq模块

堆排序

二叉树

关于二叉树的操作,其实核心就是 父节点找子节点,子节点找父节点

如果要将二叉树存储到队列中,就需要找出 父子节点之间的规律:

  • 父找子: 2i+1(父与左) ,2i+2(父与右)
  • 子找父:(i-1)//2

在这里插入图片描述

完全二叉树

在这里插入图片描述

在这里插入图片描述

构造堆:从最后一个非叶子节点开始调整

堆排序的过程:

在这里插入图片描述

代码实现
"""
堆排序
""""""
时间复杂度 :               O(N*logN)
每次调整的时候:要么走左边要么走右边,每次只会走一个树的高度(logN)
"""def sift(li, low, high):"""调整函数,无论是构建堆还是移动堆都需要这个调整函数:param low: 根节点:param high: 堆最后一个元素的位置:return:""""""1. 先把根节点拿出来2. 比较左右节点大小,选择替换3. 将拿出来的根节点放到合适位置"""i = low  # i最开始指向根节点j = 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 = j  # 往下看一层j = 2 * i + 1else:  # tmp更大,把tmp放到i的位置上li[i] = tmp  # 把tmp放到某一级领导位置上breakelse:li[i] = tmp  # 把tmp放到叶子节点上def heap_sort(li):"""1. 构建大根堆2. 调整堆为完全二叉树3."""n = len(li)for i in range((n - 1 - 1) // 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)  # 将堆空间每次减一,排序li = [i for i in range(100)]
import randomrandom.shuffle(li)
print(li)heap_sort(li)
print(li)
python中的heapq模块

python有一个内置的推排序模块,(在构建堆的时候,构建的是小根堆)

import random
import heapqli = [random.randint(1, 101) for i in range(10)]
print(li)
heapq.heapify(li)  # 建堆(小根堆)
for i in range(len(li)):tmp = heapq.heappop(li)  # 弹出一个最小元素

若有错误与不足请指出,关注DPT一起进步吧!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/451568.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

什么是SYN flood,如何处理

在数字化时代&#xff0c;随着互联网的普及和技术的飞速发展&#xff0c;网络安全问题变得日益严峻。Flood攻击&#xff0c;作为一种典型的网络攻击手段&#xff0c;对个人和企业的信息安全构成了重大威胁。通过深入了解Flood攻击的概念、特点、影响及解决方案&#xff0c;我们…

Sentinel 快速入门

前置推荐阅读:Sentinel 介绍-CSDN博客 前置推荐阅读&#xff1a;Nacos快速入门-CSDN博客 快速开始 欢迎来到 Sentinel 的世界&#xff01;这篇新手指南将指引您快速入门 Sentinel。 Sentinel 的使用可以分为两个部分: 核心库&#xff08;Java 客户端&#xff09;&#xff1a…

现代数字信号处理I-P4 CRLB+LMMSE 学习笔记

目录 学习资料视频链接&#xff1a; 1. 估计参数的CRLB回顾 2. 参数变换下的CRLB拓展 3. 矢量参数下的CRLB扩展 3.1 矢量参数下的CRLB公式 3.2 两个矩阵不等式关系的意义说明 3.3 矢量参数下CRLB公式的证明过程 4. 线性估计 重点注意事项&#xff1a;此处的线性估计&am…

【React】React18核心源码解读

前言 本文使用 React18.2.0 的源码&#xff0c;如果想回退到某一版本执行git checkout tags/v18.2.0即可。如果打开源码发现js文件报ts类型错误请看本人另一篇文章&#xff1a;VsCode查看React源码全是类型报错如何解决。 阅读源码的过程&#xff1a; 下载源码 观察 package…

【java面经thinking】二

目录 redis了解 使用原因 应用场景 数据类型 redis事务 数据持久化 RDB(快照)&#xff1a; AOF(即时更新)&#xff1a; 选择方式&#xff1a; redis快速的原因 redis单线程 单机瓶颈 经典3问 参考博客 redis了解 缓存中间件 使用原因 缓解高并发、提升高可用。…

Qt 实现动态时钟

1.实现效果 2.widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget>QT_BEGIN_NAMESPACE namespace

归一化输入

当输入的不同的特征取值范围差异过大&#xff0c;取得对应参数差别也会很大&#xff0c;在对参数进行优化的过程中&#xff0c;参数小的维度步长较小&#xff0c;参数大的维度步长较大&#xff0c;优化过程中路径曲折&#xff0c;将输入归一化&#xff0c;使特征取值范围差别小…

Leetcode 剑指 Offer II 098.不同路径

题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下…

华强北耳机最强攻略。华强北Airpods不踩坑,指南在这

#华强北Airpods##华强北耳机#这一篇文章&#xff0c;我会比较啰嗦&#xff0c;但会十分详细介绍目前能入手的渠道 和每一个渠道入手的优缺点&#xff0c;以便各位选择适合自己的渠道入手。 ■ 01 芯片ic大升级—————— 采用全新07IC板的洛达Ae芯片 整体提升三个单位算法 该…

idea-java序列化serialversionUID自动生成

&#x1f496;简介 java.io.Serializable 是 Java 中的一个标记接口&#xff08;marker interface&#xff09;&#xff0c;它没有任何方法或字段。当一个类实现了 Serializable 接口&#xff0c;那么这个类的对象就可以被序列化和反序列化。序列化是将对象的状态转换为字节流…

【原创】java+ssm+mysql小区物业管理系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…

使用 Docker-compose 部署达梦 DM 数据库

目录 1. 获取达梦 DM8 Docker 镜像并上传到 Harbor 服务器 2. Docker-compose 部署达梦 DM8 数据库 3. 配置 dm.ini 文件 4.完整的 dm.ini 文件 最近&#xff0c;将 MySQL 数据库迁移到了达梦 DM8 数据库。本文将分享如何通过 Docker-compose 部署达梦 DM8 数据库的过程&am…

全面的编程语言常识

本文首发 编程语言常识 语雀看图区别编程语言什么是强类型、弱类型语言&#xff1f;哪种更好&#xff1f;强...https://www.yuque.com/ysgstudyhard/da6e0c/ggatoo 看图区别编程语言 什么是强类型、弱类型语言&#xff1f;哪种更好&#xff1f; 强类型语言 强类型语言是一…

网络通信与并发编程(二)基于tcp的套接字、基于udp的套接字、粘包现象

基于tcp的套接字 文章目录 基于tcp的套接字一、套接字的工作流程二、基于tcp的套接字通信三、基于udp的套接字通信四、粘包现象 一、套接字的工作流程 Socket是应用层与TCP/IP协议族通信的中间软件抽象层&#xff0c;它是一组接口。在设计模式中&#xff0c;Socket其实就是一个…

【Java】多线程 Start() 与 run() (简洁实操)

Java系列文章目录 补充内容 Windows通过SSH连接Linux 第一章 Linux基本命令的学习与Linux历史 文章目录 Java系列文章目录一、前言二、学习内容&#xff1a;三、问题描述start() 方法run() 方法 四、解决方案&#xff1a;4.1 重复调用 .run()4.2 重复调用 start()4.3 正常调用…

基础数据结构——链表(单向链表,双向链表,循环链表)

1.概述 在计算机科学中&#xff0c;链表是数据元素的线性集合&#xff0c;其每个元素都指向下一个元素&#xff0c;元素存储上并不连续 分类 单向链表&#xff0c;每个元素只知道其下一个元素是谁 双向链表&#xff0c;每个元素知道其上一个元素和下一个元素 循环链表&am…

EasyExcel填充模板导出excel.xlsx

菜鸟的自我救赎&#xff0c;自从有了GPT&#xff0c;还是头一次一个bug写一天。 直接贴导出excel模板的完整案例 官网冲刺 EasyExcel EasyExcel填充模板导出excel.xlsx / 导出excel模板 一、bug(不需要请跳过) 1.1 使用apache poi操作excel报错 java.lang.NoSuchMethodError…

与双指针的亲密接触:快与慢的浪漫交错

公主请阅 1.合并两个有序数组1.1 题目说明示例 1示例 2示例 3 1.2 题目分析 1.3代码部分1.4 代码解析 2.移动零2.1题目说明示例 1示例 2 2.2题目分析2.3代码部分2.4代码解析 1.合并两个有序数组 题目传送门 1.1 题目说明 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums…

汽车免拆诊断案例 | 2022款大众捷达VS5车行驶中挡位偶尔会锁在D3挡

故障现象  一辆2022款大众捷达VS5汽车&#xff0c;搭载EA211发动机和手自一体变速器&#xff0c;累计行驶里程约为4.5万km。该车行驶中挡位偶尔会锁在D3挡&#xff0c;车速最高约50 km/h&#xff0c;且组合仪表上的发动机故障灯和EPC灯异常点亮。 故障诊断  用故障检测仪检…

linux一二三章那些是重点呢

第一章 静态库动态库的区别 什么是库 库文件是计算机上的一类文件&#xff0c;可以简单的把库文件看成一种代码仓库&#xff0c;它提供给使用者一些可以直接 拿来用的变量、函数或类。 如何制作 静态动态库 静态库&#xff1a; GCC 进行链接时&#xff0c;会把静态库中代码打…