【算法】二叉树(满二叉树和完全二叉树)、堆(堆的向下调整)、堆排序、堆的内置模块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

相关文章

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》:本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Qt spdlog日志模块的使用详解

《Qtspdlog日志模块的使用详解》在Qt应用程序开发中,良好的日志系统至关重要,本文将介绍如何使用spdlog1.5.0创建满足以下要求的日志系统,感兴趣的朋友一起看看吧... 目录版本摘要例子logmanager.cpp文件main.cpp文件版本spdlog版本:1.5.0采用1.5.0版本主要

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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 日期比较二、六大常用方法详