本篇文章给大家带来的内容是关于python中二叉堆的详细介绍（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
一、堆
数据结构 堆（heap） 是一种优先队列。队列是一种先进先出的数据结构。队列的一个重要变种称为优先级队列。使用优先队列能够以任意顺序增加对象，并且能在任意的时间（可能在增加对象的同时）找到（也可能移除）最小的元素，也就是说它比python的min方法更加有效率。
在优先级队列中，队列中的项的逻辑顺序由它们的优先级确定。最高优先级项在队列的前面，最低优先级的项在后面。因此，当你将项排入优先级队列时，新项可能会一直移动到前面。
二、二叉堆操作
我们的二叉堆实现的基本操作如下：
BinaryHeap() 创建一个新的，空的二叉堆。
insert(k) 向堆添加一个新项。
findMin()返回具有最小键值的项，并将项留在堆中。
delMin() 返回具有最小键值的项，从堆中删除该项。
如果堆是空的，isEmpty() 返回true，否则返回 false。
size() 返回堆中的项数。
buildHeap(list) 从键列表构建一个新的堆。
注意，无论我们向堆中添加项的顺序是什么，每次都删除最小的。
为了使我们的堆有效地工作，我们将利用二叉树的对数性质来表示我们的堆。为了保证对数性能，我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 在我们的堆实现中，我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树，其中 每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。 Figure 1 展示了完整二叉树的示例。
完整二叉树的另一个有趣的属性是，我们可以使用单个列表来表示它。
# from pythonds.trees.binheap import BinHeap
class 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 > 0):
self.percDown(i)
i = i - 1
def percUp(self,i):
'''如果新添加的项小于其父项，则我们可以将项与其父项交换。'''
while i // 2 > 0: # // 取整除 - 返回商的整数部分（向下取整）
if self.heapList[i] < self.heapList[i//2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2
def percDown(self, i):
'''将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。'''
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
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 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
'''移走根节点的元素（最小项）后如何保持堆结构和堆次序'''
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())关于二叉堆的最后一部分便是找到从无序列表生成一个“堆”的方法。我们首先想到的是，将无序列表中的每个元素依次插入到堆中。对于一个排好序的列表，我们可以用二分搜索找到合适的位置，然后在下一个位置插入这个键值到堆中，时间复杂度为O(logn)。另外插入一个元素到列表中需要将列表的一些其他元素移动，为新节点腾出位置，时间复杂度为O(n)。因此用insert方法的总开销是O(nlogn)。其实我们能直接将整个列表生成堆，将总开销控制在O(n)。Listing 6 所示的是生成堆的操作。
能在O(n)的开销下能生成二叉堆看起来有点不可思议，这里就不做证明了。但要理解用O(n)的开销能生成堆的关键是因为logn因子基于树的高度。而对于buildHeap里的许多操作，树的高度比logn要小。
以上是python中二叉堆的详细介绍（代码示例）的详细内容。更多信息请关注PHP中文网其他相关文章！
