python数据结构堆说明
1、堆是用数据结构来实现的一种算法:树,数组均可。堆本身是一棵完全二叉树。
2、特点,堆:所有父节点的值大于子节点的值。最小堆,所有父节点的值小于子节点的值。
python数据结构堆实例
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))
神龙|纯净稳定代理IP免费测试>>>>>>>>天启|企业级代理IP免费测试>>>>>>>>IPIPGO|全球住宅代理IP免费测试