python数据结构堆的介绍

说明

1、堆是用数据结构来实现的一种算法：树，数组均可。堆本身是一棵完全二叉树。

2、特点，堆：所有父节点的值大于子节点的值。最小堆，所有父节点的值小于子节点的值。

实例

classHeap(object):
def__init__(self,list=[]):
self.root=None
self.list=list
self.tree=None
self.len=len(list)

#建堆
defbulid_heap(self):
ifself.list!=[]:
final_parent_node=int((self.len-1)/2)
whilefinal_parent_node>=0:
self.heapfy(final_parent_node,self.len)
final_parent_node-=1

#对当前节点以及向下所有子节点的一次节点交换
defheapfy(self,node,len):
node_left=2*node+1
node_right=2*node+2
max=node
ifnode_left<lenandself.list[node_left]>self.list[max]:
max=node_left
ifnode_right<lenandself.list[node_right]>self.list[max]:
max=node_right
ifmax!=node:
self.swap(max,node)
self.heapfy(max,len)

#交换元素方法
defswap(self,i,j):
self.list[j],self.list[i]=self.list[i],self.list[j]

#堆排序
defheap_sort(self):
len=self.len-1
whilelen>=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))

以上就是python数据结构堆的介绍，希望对大家有所帮助。更多Python学习指路：Python基础教程