好资源导航 » 文章资讯 » Python数据结构与算法之完全树与最小堆实例

Python数据结构与算法之完全树与最小堆实例

2023-09-19 12:14:05 45

本文实例讲述了Python数据结构与算法之完全树与最小堆。分享给大家供大家参考，具体如下：

#完全树最小堆
classCompleteTree(list):
defsiftdown(self,i):
"""对一颗完全树进行向下调整，传入需要向下调整的节点编号i
当删除了最小的元素后，当新增加一个数被放置到堆顶时，
如果此时不符合最小堆的特性，则需要将这个数向下调整，直到找到合适的位置为止"""
n=len(self)
#当i节点有儿子（至少是左儿子时），并且有需要调整时，循环执行
t=0
whilei*2+1self[i*2+1]:
t=i*2+1
else:t=i
#如果有右儿子，则再对右儿子进行讨论
ifi*2+2self[i*2+2]:t=i*2+2
#step2：把最小的结点中的元素和结点i的元素交换
ift!=i:
self[t],self[i]=self[i],self[t]
i=t#更新i为刚才与它交换的儿子结点的编号，以便接下来继续向下调整
else:
break#说明当前父结点已经比两个子结点要小，结束调整
defsiftup(self,i):
"""对一棵完全树进行向上调整，传入一个需要向上调整的结点编号i
当要添加一个新元素后，对堆底（最后一个）元素进行调整"""
ifi==0:return
n=len(self)
ifi<0:i+=n
#注意，由于堆的特性，不需要考虑左儿子结点的情况
#由于父结点绝对比子结点小所以只需要比较一次
whilei!=0:
ifself[i]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)
printct
>>>[99,5,36,7,22,17,92,12,2,19,25,28,1,46]
ct.shufflePile()
printct
>>>[1,2,17,5,19,28,46,12,7,22,25,99,36,92]
s=ct.heapsort()
printct
>>>[1,2,5,7,12,17,19,22,25,28,36,46,92,99]

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

返回顶部
514930285
czq8825@qq.com

Python数据结构与算法之完全树与最小堆实例

热门推荐

随机推荐