python中二叉堆的详细介绍（代码示例）

# from pythonds.trees.binheap import BinHeapclass BinHeap:    def __init__(self):        self.heapList = [0]        self.currentSize = 0    def insert(self,k):        '''将项附加到列表的末尾，并通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 '''        self.heapList.append(k)        self.currentSize = self.currentSize + 1        self.percUp(self.currentSize)    def buildHeap(self, alist):        '''直接将整个列表生成堆，将总开销控制在O(n)'''        i = len(alist) // 2        self.currentSize = len(alist)        self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本        while (i &gt; 0):            self.percDown(i)           i = i - 1    def percUp(self,i):        '''如果新添加的项小于其父项，则我们可以将项与其父项交换。'''        while i // 2 &gt; 0:    # // 取整除 - 返回商的整数部分（向下取整）            if self.heapList[i]  self.heapList[mc]:                tmp = self.heapList[i]                self.heapList[i] = self.heapList[mc]                self.heapList[mc] = tmp            i = mc    def minChild(self, i):        '''在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。'''        if i * 2 + 1 &gt; self.currentSize:            return i * 2        else:            if self.heapList[i * 2] <p>关于二叉堆的最后一部分便是找到从无序列表生成一个“堆”的方法。我们首先想到的是，将无序列表中的每个元素依次插入到堆中。对于一个排好序的列表，我们可以用二分搜索找到合适的位置，然后在下一个位置插入这个键值到堆中，时间复杂度为O(logn)。另外插入一个元素到列表中需要将列表的一些其他元素移动，为新节点腾出位置，时间复杂度为O(n)。因此用insert方法的总开销是O(nlogn)。其实我们能直接将整个列表生成堆，将总开销控制在O(n)。Listing 6 所示的是生成堆的操作。</p><p>能在O(n)的开销下能生成二叉堆看起来有点不可思议，这里就不做证明了。但要理解用O(n)的开销能生成堆的关键是因为logn因子基于树的高度。而对于buildHeap里的许多操作，树的高度比logn要小。</p>