电子商务网站模板,宁波seo关键词优化,域名收录提交,旅游公司网页设计二叉堆这个数据结构有点意思#xff0c;自己做了个总结#xff0c;内容结构如下#xff1a;二叉堆性质二叉堆操作应用二叉堆性质#xff1a;堆(Heap)是一个可以被看成近似完全二叉树的结构#xff0c;具有完全二叉树的特性#xff1a;缺少的叶子节点总是位于右子节点n个节…二叉堆这个数据结构有点意思自己做了个总结内容结构如下二叉堆性质二叉堆操作应用二叉堆性质堆(Heap)是一个可以被看成近似完全二叉树的结构具有完全二叉树的特性缺少的叶子节点总是位于右子节点n个节点的完全二叉树高度k⌊ log2n⌋(向上取整)从1开始按层序编号那么第i个节点有如下性质其左子节点索引是2i其又子节点索引是2i1其父节点索引为 i // 2同时具有堆的特性堆顶元素就是最值O(1)时间就能优先拿到从根节点(堆顶)到堆中每一个节点都是一个有序序列。存储方式可以用线性的数组来实现实现简单易操作不过要注意数组下标从0开始这个位置预留占位节点的索引从1开始编号。2.pngbinarytree.png二叉堆操作BinaryHeap()创建一个空的二叉堆对象insert(key)将新元素加入到堆中findMin()返回堆中的最小项最小项仍保留在堆中delMin()返回堆中的最小项同时从堆中删除isEmpty()返回堆是否为空size()返回堆中节点的个数buildHeap(lst)从一个包含节点的列表里创建新堆# 直接导入Pythonds包使用其提供的有关堆的数据结构。from pythonds.trees import BinaryHeapbheapBinaryHeap()bheap.insert(5)#用list来实现对堆的操作class BinaryHeap(object):定义一个二叉堆def __init__(self):self.heapList [0] # 第一个堆元素从1开始编号索引为0占位不用self.currentSize 0def percolateUP(self, i):将第i个元素上浮到合适位置while i // 2 0:if self.heapList[i] self.heapList[i // 2]:self.heapList[i], self.heapList[i // 2] self.heapList[i // 2], self.heapList[i]else:breaki i // 2def percolateDown(self, i):将第i个元素下沉到合适位置while (2 * i) self.currentSize:minIndex self.minChild(i)if self.heapList[i] self.heapList[minIndex]:self.heapList[i], self.heapList[minIndex] self.heapList[minIndex], self.heapList[i]else:breaki minIndexdef minChild(self, i):返回第i个元素左右子节点中最小值if (2 * i 1) self.currentSize:return 2 * i # 只有一个子节点(左子节点)elif self.heapList[2 * i] self.heapList[2 * i 1]:return 2 * ielse:return 2 * i 1def insert(self, key):将新元素加入到堆中self.heapList.append(key)self.currentSize self.currentSize 1self.percolateUP(self.currentSize) # 新值上浮def findMin(self):返回堆中的最小项最小项仍保留在堆中return heapList[1]def delMin(self):返回堆中的最小项同时从堆中删除result self.heapList[1]# 将最后一个元素换到堆顶并删除堆顶元素self.heapList[1] self.heapList.pop()self.currentSize self.currentSize - 1self.percolateDown(1) # 将堆顶元素下沉return resultdef isEmpty(self):返回堆是否为空return len(heapList) 1def size(self):返回堆中节点的个数return len(heapList) - 1def printHeap(self):print(self.heapList[1:])def buildHeap(self, lst):从一个包含节点的列表里创建新堆,用下沉法将时间复杂度控制在O(n)self.currentSize len(lst)i self.currentSize // 2 #从最后一个节点的父节点开始过滤下沉self.heapList [0] lst[:]while i 0:self.percolateDown(i)i i - 1self.printHeap()应用之一-----------------优先队列可以在O(1)时间拿到最值获取最优解实现对VIP或者进程的优先级等操作pic_19.png应用之二-----------------堆排序
