黑松山资源网 Design By www.paidiu.com
本文实例讲述了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相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- 【原神】V5.0攻略 | 林尼攻略一图流
- 李翊君.1993-相思的烈酒【上华】【WAV+CUE】
- 古巨基.1998-LEO.KU(国)【千禧年代】【WAV+CUE】
- 郭子.2001-原来你什么都不想要创作集丫滚石】【WAV+CUE】
- 《使命召唤:黑色行动6》新预告公布!10月25日发售
- Atlus《暗喻幻想》媒体评分汇总:高分好评如潮!
- 2024金摇杆奖提名揭晓 《黑神话》角逐最佳视觉设计!
- 群星《新说唱2024 第3期 (上)》[320K/MP3][32.76MB]
- 群星《新说唱2024 第3期 (上)》[FLAC/分轨][95.38MB]
- 群星《新说唱2024 第3期 (下)》[320K/MP3][31.36MB]
- 幻兽帕鲁手游什么时候正式上线 最新消息一览
- 西普大陆BOSS位置盘点 解锁天启纪元玩法
- 西普大陆精灵进阶培养攻略 精灵养成指南
- dnf手游法控法系职业哪个强 dnf手游法控法系职业强度排行
- 魔兽世界血藤护目镜图纸在哪买 wlk血藤护目镜图纸购买位置介绍