【算法】二叉树(满二叉树和完全二叉树)、堆(堆的向下调整)、堆排序、堆的内置模块heapq

2024-08-23 10:44

本文主要是介绍【算法】二叉树(满二叉树和完全二叉树)、堆(堆的向下调整)、堆排序、堆的内置模块heapq,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1 二叉树
1.1 满二叉树和完全二叉树
1.2 堆的向下调整
2 堆排序
3 堆的内置模块

1 二叉树

二叉树是一种树形数据结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树的常见类型包括:
1. **普通二叉树**:任意一种二叉树,没有特定的性质约束。
2. **完全二叉树**:除了最后一层,其他层的节点都是满的,且最后一层的节点尽可能向左排列。
3. **满二叉树**:每一层的节点数都达到最大值,即每个节点要么有两个子节点,要么没有子节点。
4. **平衡二叉树(AVL树)**:一种自平衡的二叉搜索树,任何节点的两个子树的高度差不超过1。
5. **二叉搜索树(BST)**:对于每个节点,左子节点的值小于该节点的值,右子节点的值大于该节点的值。
6. **红黑树**:一种特殊的二叉搜索树,通过额外的“红”或“黑”标记来保持树的平衡,使得最长路径不超过最短路径的两倍。这些二叉树类型在算法和数据结构中用于实现高效的搜索、排序和数据管理操作。

1.1 满二叉树和完全二叉树

在这里插入图片描述

在这里插入图片描述

1.2 堆的向下调整

在这里插入图片描述

向下调整为下图注意观察树的变化

在这里插入图片描述

2 堆排序

"""
满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。
完全二叉树:叶节点只能出现在最下层的次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。二叉树的存储方式:链式存储方式顺序存储方式堆:一种特殊的完全二叉树堆排序(Heap Sort)是一种基于堆数据结构的比较排序算法,具有优良的时间复杂度表现。
堆是一种特殊的完全二叉树结构,可以分为两种类型:
最大堆:每个节点的值都大于或等于其子节点的值。
最小堆:每个节点的值都小于或等于其子节点的值。堆排序通常使用最大堆来进行排序。
其基本步骤如下:
步骤1:构建最大堆首先,将待排序数组构建成最大堆。这一步的目的是将数组中的最大元素移动到根节点(即数组的第一个位置)。
步骤2:交换堆顶元素和最后一个元素将堆顶(最大元素)与堆的最后一个元素交换,然后将堆的大小减一,排除最后一个元素,因为它已经处于正确的位置。
步骤3:调整堆对堆顶元素进行调整,使剩余的元素仍然保持最大堆的性质。这个过程通常称为“堆化”或“下沉”。
步骤4:重复步骤2和步骤3重复步骤2和步骤3,直到所有元素都排好序。时间复杂度堆排序的时间复杂度为 O(nlogn),其中 n 是待排序元素的数量。它在最坏、最好和平均情况下的时间复杂度都是 O(nlogn),并且它是一种不稳定的排序算法。
"""def sift(li: list, low: int, high: int):""":param li:列表:param low:堆的根节点位置:param high:堆的最后一个元素的位置:return:"""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: list):n = len(li)for i in range((n - 2) // 2, -1, -1):# i表示建堆的时候调整的部分的根的下标sift(li, i, n - 1)# 建堆完成了print(li)for i in range(n - 1, -1, -1):# i 指向当前堆的最后一个元素li[0], li[i] = li[i], li[0]sift(li, 0, i - 1)  # i-1是新的highli = [i for i in range(100)]
import randomrandom.shuffle(li)
print(li)
heap_sort(li)
print(li)

3 堆的内置模块

import heapq  # q->queue 优先队列
import randomli = list(range(100))
random.shuffle(li)print(li)heapq.heapify(li)  # 建堆n = len(li)
for i in range(n):print(heapq.heappop(li), end=',')

这篇关于【算法】二叉树(满二叉树和完全二叉树)、堆(堆的向下调整)、堆排序、堆的内置模块heapq的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099154

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

python中的整除向下取整的操作方法

《python中的整除向下取整的操作方法》Python中的//是整数除法运算符,用于执行向下取整的除法,返回商的整数部分,不会四舍五入,它在分治法、索引计算和整数运算中非常有用,本文给大家介绍pyth... 目录1. // 的基本用法2. // vs /(普通除法)3. // 在 mid = len(lis

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Python批量调整Word文档中的字体、段落间距及格式

《Python批量调整Word文档中的字体、段落间距及格式》这篇文章主要为大家详细介绍了如何使用Python的docx库来批量处理Word文档,包括设置首行缩进、字体、字号、行间距、段落对齐方式等,需... 目录关键代码一级标题设置  正文设置完整代码运行结果最近关于批处理格式的问题我查了很多资料,但是都没

Node.js net模块的使用示例

《Node.jsnet模块的使用示例》本文主要介绍了Node.jsnet模块的使用示例,net模块支持TCP通信,处理TCP连接和数据传输,具有一定的参考价值,感兴趣的可以了解一下... 目录简介引入 net 模块核心概念TCP (传输控制协议)Socket服务器TCP 服务器创建基本服务器服务器配置选项服