导语:
本文主要介绍了关于python数据结构堆的介绍的相关知识,包括数据结构有哪些,以及python算法与数据结构这些编程知识,希望对大家有参考作用。
说明
1.堆是通过数据结构实现的算法:树或数组。堆本身是一棵完全二叉树。
2.特征,堆:所有父节点的值都大于子节点的值。一个最小堆,所有父节点的值都小于子节点。
实例
class Heap(object):
def __init__(self, list=[]):
self.root = None
self.list = list
self.tree = None
self.len = len(list)
# 建堆
def bulid_heap(self):
if self.list != []:
final_parent_node = int((self.len - 1) / 2)
while final_parent_node >= 0:
self.heapfy(final_parent_node, self.len)
final_parent_node -= 1
# 对当前节点以及向下所有子节点的一次节点交换
def heapfy(self, node, len):
node_left = 2 * node + 1
node_right = 2 * node + 2
max = node
if node_left < len and self.list[node_left] > self.list[max]:
max = node_left
if node_right < len and self.list[node_right] > self.list[max]:
max = node_right
if max != node:
self.swap(max, node)
self.heapfy(max, len)
# 交换元素方法
def swap(self, i, j):
self.list[j], self.list[i] = self.list[i], self.list[j]
# 堆排序
def heap_sort(self):
len = self.len - 1
while len >= 0:
self.swap(0, len)
self.heapfy(0, len)
len -= 1
if __name__ == "__main__":
list = [5, 7, 3, 1, 10, 0]
heap = Heap(list)
print("初始列表:{}".format(heap.list))
heap.bulid_heap()
print("堆化:{}".format(heap.list))
heap.heap_sort()
print("排序:{}".format(heap.list))
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
本文为原创文章,版权归知行编程网所有,欢迎分享本文,转载请保留出处!
你可能也喜欢
- ♥ Python创建两种形式的链表12/10
- ♥ 如何在python中使用reverse函数?08/12
- ♥ 如何停止python程序09/03
- ♥ python break 和 continue 的比较09/13
- ♥ 如何从python中的数组中删除指定元素10/03
- ♥ python打开文件的两种方式08/26
内容反馈