Python数据结构与算法之完全树与最小堆实例
作者:hanahimi 发布时间:2021-01-10 06:58:47
标签:Python,完全树
本文实例讲述了Python数据结构与算法之完全树与最小堆。分享给大家供大家参考,具体如下:
# 完全树 最小堆
class CompleteTree(list):
def siftdown(self,i):
""" 对一颗完全树进行向下调整,传入需要向下调整的节点编号i
当删除了最小的元素后,当新增加一个数被放置到堆顶时,
如果此时不符合最小堆的特性,则需要将这个数向下调整,直到找到合适的位置为止"""
n = len(self)
# 当 i 节点有儿子(至少是左儿子时),并且有需要调整时,循环执行
t = 0
while i*2+1<n:
# step 1:从当前结点,其左儿子,其右儿子中找到最小的一个,将其编号传给t
if self[i] > self[i*2+1]:
t = i*2+1
else: t = i
# 如果有右儿子,则再对右儿子进行讨论
if i*2+2<n:
if self[t] > self[i*2+2]: t = i*2+2
# step 2:把最小的结点中的元素和结点i的元素交换
if t != i:
self[t],self[i] = self[i],self[t]
i = t # 更新i为刚才与它交换的儿子结点的编号,以便接下来继续向下调整
else:
break # 说明当前父结点已经比两个子结点要小,结束调整
def siftup(self,i):
""" 对一棵完全树进行向上调整,传入一个需要向上调整的结点编号i
当要添加一个新元素后,对堆底(最后一个)元素进行调整 """
if i==0: return
n = len(self)
if i < 0: i += n
# 注意,由于堆的特性,不需要考虑左儿子结点的情况
# 由于父结点绝对比子结点小所以只需要比较一次
while i!=0:
if self[i]<self[(i-1)/2]:
self[i],self[(i-1)/2] = self[(i-1)/2],self[i]
else:
break
i = (i-1)/2 # 更新i为其父结点编号,从而便于下一次继续向上调整
def shufflePile(self):
""" 在当前状态下,对树调整使其成为一个堆 """
# 从"堆底"往"堆顶"进行向下调整,使得最小的元素不断上升
# 这样可以使得i结点以下的堆是局部最小堆
for i in range((len(self)-2)/2,-1,-1): # n/2,...,0
self.siftdown(i)
def deleteMin(self):
""" 删除最小元素 """
t = self[0] # 用一个临时变量记录堆顶点的
self[0] = self[-1] # 将堆的最后一个点赋值到堆顶
self.pop() # 删除最后一个元素
self.siftdown(0) # 向下调整
return t
def heapsort(self):
""" 对堆中元素进行堆排序操作 """
n = len(self)
s = []
while n>0:
s.append(self.deleteMin())
n -= 1
# 由于堆中的元素已全部弹出,将排序好的元素拼接到原来的堆中
self.extend(s)
if __name__=="__main__":
a = [99,5,36,7,22,17,92,12,2,19,25,28,1,46]
ct = CompleteTree(a)
print ct
>>> [99, 5, 36, 7, 22, 17, 92, 12, 2, 19, 25, 28, 1, 46]
ct.shufflePile()
print ct
>>> [1, 2, 17, 5, 19, 28, 46, 12, 7, 22, 25, 99, 36, 92]
s = ct.heapsort()
print ct
>>> [1, 2, 5, 7, 12, 17, 19, 22, 25, 28, 36, 46, 92, 99]
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hanahimi/p/4692668.html
0
投稿
猜你喜欢
- chatGPT已经爆火一段时间了,我想大多数的开发者都在默默的在开发和测试当中,可能也是因为这个原因所以现在很难找到关于开发中遇到的一些坑或
- 我在使用python3.5处理一个序列化文件xxx.pk,不过这个.pk文件是我在python2.7里面存储的,当我用python3读取的时
- 聚集索引,数据实际上是按顺序存储的,数据页就在索引页上。就好像参考手册将所有主题按顺序编排一样。一旦找到了所要搜索的数据,就完成了这次搜索,
- 这份代码不是那种时间没有改变也输出innerHTML的高消耗代码。innerHTML和style的改变是非常消耗游览器性能的,如果你将来希望
- 一般情况下,运行tensorflow时,默认会占用可以看见的所有GPU,那么就会导致其它用户或程序无GPU可用,那么就需要限制程序对GPU的
- 一条语句搞定数据库分页select top 10 b.* from (select&nbs
- 前言图像分割是许多计算机视觉应用中的关键处理步骤,通常用于将图像划分为不同的区域,这些区域常常对应于真实世界的对象。因此,图像分割是图像识别
- 本文为大家讲解了pytorch实现CNN卷积神经网络,供大家参考,具体内容如下我对卷积神经网络的一些认识卷积神经网络是时下最为流行的一种深度
- 在域环境下我没配置成果,也许是域用户的原因,因为我在生产环境下搞的,更改域用户需要重启SQLServer ,所以这个方法放弃了,只能用证书形
- 类:定义一件事物的抽象特点。对象:类的 实例。成员变量 − 定义在类内部的变量。该变量的值对外是不可见的,但是可以通过成
- 1、epochKeras官方文档中给出的解释是:“简单说,epochs指的就是训练过程接中数据将被“轮”多少次”(1)释义:训练过程中当一个
- 以前见过一个很漂亮的网页提示信息,就是把鼠标放到网页的文字或者图片上面就会有提示的那种透明的,还带个箭头,很漂亮,不知道谁在哪见过没有,感谢
- 项目整体布局创建并进入项目文件夹:$ mkdir flask-tutorial$ cd flask-tutorial接下来按照 安装简介 设
- 在跨业务、跨网站发送数据或者业务升级的时候,我们有的时候需要指定发送数据的编码方式,比如页面是utf-8编码的,而发送出去的数据却是GB23
- 1.func Fields(s string) []string,这个函数的作用是按照1:n个空格来分割字符串最后返回的是[]string的
- 前言上篇文章讲的进阶一些的PHP特性不知道大家吸收的怎么样了,今天作为本PHP特性函数的最后一篇,我也会重点介绍一些有趣的PHP特性以及利用
- 问题:pycharm无法调用pip安装的包原因:pycharm没有设置解析器解决方法:打开pycharm->File->Sett
- 有时候希望可以用js另开新窗口,但用window.open方法打开窗口总是被浏览器阻止,可以用下面的方法打开新窗口而不会遭到拦截1.新添加一
- PyCharm是Python著名的Python集成开发环境(IDE)conda有Miniconda和Anaconda,前者应该是类似最小化版
- <?php// 使用Memache 作为进程锁 class lock_processlock{// key 的前缀protected