python实现堆排序的实例讲解

堆排序

堆是一种完全二叉树（是除了最后一层，其它每一层都被完全填充，保持所有节点都向左对齐），首先需要知道概念：最大堆问题，最大堆就是根节点比子节点值都大，并且所有根节点都满足，那么称它为最大堆。反之最小堆。

当已有最大堆，如下图，首先将7提出，然后将堆中最后一个元素放到顶点上，此时这个堆不满足最大堆了，那么我们要给它构建成最大堆，需要找到此时堆中对打元素然后交换，此时最大值为6，符合最大堆后，我们将6提取出来，然后将堆中最后一个元素放到堆的顶部...以此类推。最后提取的数值7,6,5,4,3,2,1

那么在维护一个最大堆过程中，最多进行交换次数决定了此算法复杂度，但交换次数与树的高度有关：

​ h=log2(n+1)h=log2(n+1)

最大堆生成：根据最大堆特性(任意一个根节点都大于叶子节点)不满足就调换。

代码实现：

from collections import deque

def swap_param(L, i, j):
 # 堆顶与最后元素交换
 L[i], L[j] = L[j], L[i]
 return L

def heap_adjust(L, start, end):
 #构造成大根堆
 temp = L[start]
 i = start
 j = 2 * i
 while j <= end:
 # 判断左右子节点，取两个子节点最大索引
 if (j < end) and (L[j] < L[j + 1]):
  j += 1
 # 判断根节点与子节点比较，如果子节点大于根节点，子节点赋值给根节点
 if temp < L[j]:
  L[i] = L[j]
  i = j
  j = 2 * i
 else:
  break
 # 再把 原来根节点值赋值给子节点上
 L[i] = temp

def heap_sort(L):
 L_length = len(L) - 1

 first_sort_count = L_length // 2
 for i in range(first_sort_count):
 heap_adjust(L, first_sort_count - i, L_length)

 for i in range(L_length - 1):
 L = swap_param(L, 1, L_length - i)
 heap_adjust(L, 1, L_length - i - 1)

 return [L[i] for i in range(1, len(L))]

def main():
 L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
 L.appendleft(0)
 print(heap_sort(L))

main()

基础知识点扩展：

堆排序

堆

堆栈是计算机的两种最基本的数据结构。堆的特点就是FIFO(first in first out)先进先出，这里的话我觉得可以理解成树的结构。堆在接收数据的时候先接收的数据会被先弹出。

堆排序节点访问和操作定义

堆节点的访问

在这里我们借用wiki的定义来说明：

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中

  • 父节点i的左子节点在位置(2*i+1);
  • 父节点i的右子节点在位置(2*i+2);
  • 子节点i的父节点在位置floor((i-1)/2);

到此这篇关于python实现堆排序的实例讲解的文章就介绍到这了,更多相关堆排序python实现内容请搜素我们以前的文章或下面相关文章，希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python实现堆排序的实例讲解

    python实现堆排序的实例讲解

    堆排序 堆是一种完全二叉树(是除了最后一层,其它每一层都被完全填充,保持所有节点都向左对齐),首先需要知道概念:最大堆问题,最大堆就是根节点比子节点值都大,并且所有根节点都满足,那么称它为最大堆.反之最小堆. 当已有最大堆,如下图,首先将7提出,然后将堆中最后一个元素放到顶点上,此时这个堆不满足最大堆了,那么我们要给它构建成最大堆,需要找到此时堆中对打元素然后交换,此时最大值为6,符合最大堆后,我们将6提取出来,然后将堆中最后一个元素放到堆的顶部...以此类推.最后提取的数值7,6,5,4,3,

  • Python 模拟购物车的实例讲解

    Python 模拟购物车的实例讲解

    1.功能简介 此程序模拟用户登陆商城后购买商品操作.可实现用户登陆.商品购买.历史消费记查询.余额和消费信息更新等功能.首次登陆输入初始账户资金,后续登陆则从文件获取上次消费后的余额,每次购买商品后会扣除相应金额并更新余额信息,退出时也会将余额和消费记录更新到文件以备后续查询. 2.实现方法 架构: 本程序采用python语言编写,将各项任务进行分解并定义对应的函数来处理,从而使程序结构清晰明了.主要编写了六个函数: (1)login(name,password) 用户登陆函数,实现用户名和密码

  • Python文件和流(实例讲解)

    1.文件写入 #打开文件,路径不对会报错 f = open(r"C:\Users\jm\Desktop\pyfile.txt","w") f.write("Hello,world!\n") f.close() 2.文件读取 #读取 f = open(r"C:\Users\jm\Desktop\pyfile.txt","r") print(f.read()) f.close() 输出: Hello,world

  • python之Character string(实例讲解)

    1.python字符串 字符串是 Python 中最常用的数据类型.我们可以使用引号('或")来创建字符串,l Python不支持单字符类型,单字符也在Python也是作为一个字符串使用. >>> var1 = 'hello python' #定义字符串 >>> print(var1[0]) #切片截取,从0开始,不包括截取尾数 h >>> print(var1[0:5]) hello >>> print(var1[-6:]

  • python用户管理系统的实例讲解

    python用户管理系统的实例讲解

    学Python这么久了,第一次写一个这么多的代码(我承认只有300多行,重复的代码挺多的,我承认我确实垃圾),但是也挺不容易的 自定义函数+装饰器,每一个模块写的一个函数 很多地方能用装饰器(逻辑跟不上,有的地方没用),包括双层装饰器(不会),很多地方需要优化,重复代码太多 我还是把我的流程图拿出来吧,虽然看着比上次的垃圾,但是我也做了一个小时,不容易! 好像是挺丑的(表示不会画,但我下次一定努力) 用户文件: 文件名为:user.txt 1代表管理员用户 2代表普通用户 smelond|adm

  • 在Windows中设置Python环境变量的实例讲解

    在 Windows 设置环境变量 在环境变量中添加Python目录: 在命令提示框中(cmd) : 输入 path=%path%;C:\Python 按下"Enter". 注意: C:\Python 是Python的安装目录. 也可以通过以下方式设置: • 右键点击"计算机",然后点击"属性" • 然后点击"高级系统设置" • 选择"系统变量"窗口下面的"Path",双击即可! • 然后

  • 使用Python读取二进制文件的实例讲解

    目标:目标文件为一个float32型存储的二进制文件,按列优先方式存储.本文使用Python读取该二进制文件并使用matplotlib.pyplot相关工具画出图像 工具:Python3, matplotlib,os,struct,numpy 1. 读取二进制文件 首先使用open函数打开文件,打开模式选择二进制读取"rb". f = open(filename, "rb") 第二步,需要打开按照行列读取文件,由于是纯二进制文件,内部不含邮任何的数据结构信息,因此我

  • OpenCV+python手势识别框架和实例讲解

    基于OpenCV2.4.8和 python 2.7实现简单的手势识别. 以下为基本步骤 1.去除背景,提取手的轮廓 2. RGB->YUV,同时计算直方图 3.进行形态学滤波,提取感兴趣的区域 4.找到二值化的图像轮廓 5.找到最大的手型轮廓 6.找到手型轮廓的凸包 7.标记手指和手掌 8.把提取的特征点和手势字典中的进行比对,然后判断手势和形状 提取手的轮廓 cv2.findContours() 找到最大凸包cv2.convexHull(),然后找到手掌和手指的相对位置,定位手型的轮廓和关键点

  • python 列表降维的实例讲解

    列表降维(python:3.x) 之前遇到需要使用列表降维的情况, 如: 原列表 : [[12,34],[57,86,1],[43,22,7],[1,[2,3]],6] 转化为 : [12, 34, 57, 86, 1, 43, 22, 7, 1, 2, 3, 6] 思路: 把列表转化为字符串,直接去掉 "[" 和 "]" 最后由字符串转化为列表 a = [[12,34],[57,86,1],[43,22,7],[1,[2,3]],6] #把列表转为字符串 b =

  • Anaconda下配置python+opencv+contribx的实例讲解

    先吐槽一下opencv 3.1.0的版本cv2.sift和surf就不能用了 看解释是说 什么 "non-free",,必须要到opencv_contrib库中才有,而这个库的编译不是一点点的困难 堪称史上最恶 这几天为了装open_contrib反复编译各种报错已经很无奈了. 查遍了各种大神的各种攻略,花积分下载了各种攻略..基本上没有一个能全部解决的办法. 回帖或者其他的 要么只说 ""我解决了 " 并不说方法,要么就是不详不尽 或者比较高深 其实吧

随机推荐