首页 > 编程语言 >堆排序python实现

堆排序python实现

时间:2024-09-01 17:51:02浏览次数:10  
标签:tmp python 位置 堆排序 li 叶子 实现 二叉树 节点

一,树与二叉树

1,树

        树是一种数据结构,比如目录结构。

        树是由n各节点组成的集合:

        1.如果n = 0 ,那存在一个节点作为数的根节点,其他节点可以分为m个集合,每个集合本身又是一颗树,比如:

树的相关概念,比如根节点,叶子节点什么的不做过多介绍。

2,二叉树

 二叉树:度不超过2的树,也就是每个节点最多有两个孩子节点,两个孩子节点被区分为左孩子节点和右孩子节点。

满二叉树:一个二叉树,如果每一层的节点数都达到最大值。

完全二叉树:叶子节点只能出现在最下层和次下层,并且最下面的一层节点都集中在该层最左边的若干位置的二叉树。

二叉树
二叉树
满二叉树
完全二叉树

3,二叉树的存储方式(表示方式)

        二叉树的存储方式有链式存储方式和顺序存储方式,本文这里应用顺序存储方式。

父节点和左孩子节点的下表编号的关系:i ---> 2*i + 1

父节点和右孩子节点的下表编号的关系:i ---> 2*i + 2

二,堆排序

大根堆:一棵完全二叉树,满足任一节点都比其孩子节点大。

小根堆:一棵完全二叉树,满足任一节点都比其孩子节点小。

1,堆的向下调整

        当根节点的左右子树都是堆时,可以通过一次向下的调整将其变成一个堆。过程与下面构造堆一起说。

2,出数

        挨个出数,对于一个大根堆,根节点是最大的数,先取出,然后把底层最右边的(也就是最后一个数)叶子节点放到根节点的位置,此时左右子树都是堆,然后再进行调整为一个新的堆,再取出新堆的根节点的数,依次进行,直到取完所有数。

3,构造堆

        例如构造大根堆,采取农村包围城市的方法,从下往上调整。先看最后一个非叶子节点,对其子树进行调整。

图1
图2

        首先对于图一,开始不是一个堆,先看其中蓝红黄色框里面的子树,让子树中数大的叶子节点与根节点交换位置,其中3和5换位置,1和7换位置变成图二。

        在图二中由于“农村地区已经处理完了”,再往上看一级,红色框部分,让8和9做交换,之后再看蓝色框部分,让6与9做交换,由于6<8,所以再让6和8做交换,至此完成堆的调整。

构造完成后的堆

        再说取数向下调整,我们先把9取出去,让3(堆中最后一个叶子节点的数)去9的根节点位置,可知此时根节点的左右子树都是堆,所以可以进行一次向下调整,让根节点下面数较大的节点与其交换(前提是这个较大的数大于根节点的数),8>7,所以3和8交换位置,6>5,所以3和6交换位置,4>2,所以4和3交换位置,至此完成一次调整。

调整前
调整后

然后再取出8(第二大的数),再让3(堆中最后一个叶子节点的数)去到根节点的位置,在进行调整,依次进行,可以按顺序取出所有数。

4,代码实现

        为了节省空间,可以使用一个指针指向最后一个叶子节点,在取出数的同时把取出的数放在最后的位置,把标记最后一个数的指针向前指一个位置。例如,开始的时候标记最后的数的指针指向3,我们把9取出后,让3上去做调整,把9存放在3原来的位置,并且把指向最后面节点的指针往前指一位,依次进行。

取数前
取数且完成一次调整后

        第一步,向下调整的实现:首先要有指针指向根节点和最后一个叶子节点,令low指向根节点,high指向最后一个叶子节点,令i = low,tmp = li[low],则根节点的左孩子为j = 2 * i + 1,右孩子为j = 2 * i + 2,判断左孩子和右孩子哪个更大,让较大的那个数去i的位置,然后更新i为较大孩子的节点下标。

        循环结束条件:1.如果j > high,说明数组越界,结束循环。2.如果某个节点的左后孩子都小于tmp,令这个节点的数等于tmp,结束循环。

# 第一步,实现向下调整
def sift(li, low, high):
    """
    大根堆的调整过程
    :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 = i * 2 + 1
        else:   # tmp更大,把tmp放到i的位置上
            li[i] = tmp
            break
    else:
        li[i] = tmp   # 把tmp放到节点上

第二步,建造堆:首先要根据孩子节点位置下标 j 找到父亲节点位置下标 i ,关系为 i = (j-1) // 2,根据农村包围城市的走法从最后一个非叶子节点一次往上进行堆调整,最后整体成为一个堆,其中最后一个节点的位置下标如果是 j ,那么最后一个非叶子节点的下标就是 i = (j-1) // 2。(本人建立的是大根堆)

第三步,挨个出数:对于一个调整好的堆,先有一个指针指向最后一个叶子节点,让最后一个叶子节点的数与根节点的数交换,然后让指针指向最后一个叶子节点的前一个节点,作为要进行向下调整的数的最后一个叶子节点(相当于节点交换之后,最后一个节点放的是最大的数,此时这个节点不参与向下调整的过程,下面的过程同理)然后进行向下调整,此时根节点位置的数应该是整个数组中第二大的数,让这个数与此时的最后一个根节点的数进行交换,依次进行。

def heap_sort(li):   # 堆排序
    # 第二步,构造堆
    n = len(li)
    for 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]    # 将i所指的元素与堆顶元素交换
        sift(li, 0, i - 1)    # i-1是新的high,相当于去掉i所指过的节点,重新调整堆,保证列表中的元素按顺序排列


# 代码检验
import random
li = [i for i in range(100)]
random.shuffle(li)
print(li)
heap_sort(li)
print(li)

最后,堆排序的时间复杂度为:O(nlogn)

标签:tmp,python,位置,堆排序,li,叶子,实现,二叉树,节点
From: https://blog.csdn.net/qq_57331743/article/details/141779438

相关文章

  • 基于yolov10的学生课堂行为检测系统,支持图像检测,也支持视频和摄像实时检测(pytorch框架
       更多目标检测和图像分类识别项目可看我主页其他文章功能演示:基于yolov10的学生课堂行为检测系统,支持图像、视频和摄像实时检测【pytorch框架、python】_哔哩哔哩_bilibili(一)简介基于yolov10的学生课堂行为检测系统是在pytorch框架下实现的,这是一个完整的项目,包括代码......
  • 计算机毕业设计选题推荐-个人健康档案管理系统-Java/Python项目实战
    ✨作者主页:IT研究室✨个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。☑文末获取源码☑精彩专栏推荐⬇⬇⬇Java项目Python项目安卓项目微信小程序项目......
  • 计算机毕业设计选题推荐-公司考勤管理系统-Java/Python项目实战
    ✨作者主页:IT研究室✨个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。☑文末获取源码☑精彩专栏推荐⬇⬇⬇Java项目Python项目安卓项目微信小程序项目......
  • 计算机毕业设计选题推荐-果树生长信息管理系统-Java/Python项目实战
    ✨作者主页:IT毕设梦工厂✨个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。☑文末获取源码☑精彩专栏推荐⬇⬇⬇Java项目Python项目安卓项目微信小程序项目......
  • 计算机毕业设计选题推荐-客栈管理系统-酒店预订-民宿管理系统-Java/Python项目实战
    ✨作者主页:IT毕设梦工厂✨个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。☑文末获取源码☑精彩专栏推荐⬇⬇⬇Java项目Python项目安卓项目微信小程序项目......
  • 【Python】Flask 快速入门
    Flask介绍Flask是一个轻量级的PythonWeb框架,非常适合快速开发和小型应用。官网:https://flask.palletsprojects.com/en/3.0.x/中文文档:https://dormousehole.readthedocs.io/en/latest/教程:https://www.runoob.com/flask/flask-tutorial.htmlFlask框架......
  • 【Python】Scrapy 快速入门
    Scrapy介绍Scrapy是一个强大的Python爬虫框架官网:https://scrapy.org/官方文档:https://docs.scrapy.org/en/latest/intro/tutorial.html教程参考:https://www.runoob.com/w3cnote/scrapy-detail.htmlScrapy架构概览Scrapy中的数据流由执行引擎......
  • 基于微信小程序的古代天文知识科普系统设计与实现 120b0
    博主介绍......
  • 微信小程序的四六级网上报名系统的设计与实现 k54bj
    技术栈支持以下技术栈开发运行:微信开发者/hbuilderx前端开发框架:vue.js数据库mysql版本不限后端语言框架支持:1java(SSM/springboot)-idea/eclipse2.Nodejs+Vue.js-vscode3.python(flask/django)–pycharm/vscode4.php(thinkphp/laravel)-hbuilderx数据库工具......
  • 几分钟带你入门python GUI框架tkinter
    一、Tkinter是什么?Tkinter是Python的标准GUI库。Python与Tkinter结合使用时,提供了一种快速简便的方法来创建GUI应用程序。Tkinter为TkGUI工具包提供了一个强大的面向对象的接口。二、使用Tkinter创建GUI应用程序的基本步骤:1.安装python首先,确保你已经安......