二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
优先队列的二叉堆实现
在前面的章节里我们学习了“先进先出”（fifo）的数据结构：队列（queue）。队列有一种变体叫做“优先队列”（priority queue）。优先队列的出队（dequeue）操作和队列一样，都是从队首出队。但在优先队列的内部，元素的次序却是由“优先级”来决定：高优先级的元素排在队首，而低优先级的元素则排在后面。这样，优先队列的入队（enqueue）操作就比较复杂，需要将元素根据优先级尽量排到队列前面。我们将会发现，对于下一节要学的图算法中的优先队列是很有用的数据结构。
我们很自然地会想到用排序算法和队列的方法来实现优先队列。但是，在列表里插入一个元素的时间复杂度是o(n)，对列表进行排序的时间复杂度是o(nlogn)。我们可以用别的方法来降低时间复杂度。一个实现优先队列的经典方法便是采用二叉堆（binary heap）。二叉堆能将优先队列的入队和出队复杂度都保持在o(logn)。
二叉堆的有趣之处在于，其逻辑结构上像二叉树，却是用非嵌套的列表来实现。二叉堆有两种：键值总是最小的排在队首称为“最小堆（min heap）”，反之，键值总是最大的排在队首称为“最大堆（max heap）”。在这一节里我们使用最小堆。
二叉堆的操作
二叉堆的基本操作定义如下：
binaryheap()：创建一个空的二叉堆对象
insert(k)：将新元素加入到堆中
findmin()：返回堆中的最小项，最小项仍保留在堆中
delmin()：返回堆中的最小项，同时从堆中删除
isempty()：返回堆是否为空
size()：返回堆中节点的个数
buildheap(list)：从一个包含节点的列表里创建新堆
下面所示代码是二叉堆的示例。可以看到无论我们以哪种顺序把元素添加到堆里，每次都是移除最小的元素。我们接下来要来实现这个过程。
from pythonds.trees.binheap import binheap
bh = binheap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)
print(bh.delmin())
print(bh.delmin())
print(bh.delmin())
print(bh.delmin())
为了更好地实现堆，我们采用二叉树。我们必须始终保持二叉树的“平衡”，就要使操作始终保持在对数数量级上。平衡的二叉树根节点的左右子树的子节点个数相同。在堆的实现中，我们采用“完全二叉树”的结构来近似地实现“平衡”。完全二叉树，指每个内部节点树均达到最大值，除了最后一层可以只缺少右边的若干节点。图 1 所示是一个完全二叉树。
class binheap:
def init(self):
self.heaplist = [0]
self.currentsize = 0
我们接下来要实现的是insert方法。首先，为了满足“完全二叉树”的性质，新键值应该添加到列表的末尾。然而新键值简单地添加在列表末尾，显然无法满足堆次序。但我们可以通过比较父节点和新加入的元素的方法来重新满足堆次序。如果新加入的元素比父节点要小，可以与父节点互换位置。图 3 所示的是一系列交换操作来使新加入元素“上浮”到正确的位置。
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
listing 3
def insert(self,k):
self.heaplist.append(k)
self.currentsize = self.currentsize + 1
self.percup(self.currentsize)
我们已经写好了insert方法，那再来看看delmin方法。堆次序要求根节点是树中最小的元素，因此很容易找到最小项。比较困难的是移走根节点的元素后如何保持堆结构和堆次序，我们可以分两步走。首先，用最后一个节点来代替根节点。移走最后一个节点保持了堆结构的性质。这么简单的替换，还是会破坏堆次序。那么第二步，将新节点“下沉”来恢复堆次序。图 4 所示的是一系列交换操作来使新节点“下沉”到正确的位置。
def percdown(self,i):
while (i * 2) 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
listing 5 所示的是delmin操作的代码。可以看到比较麻烦的地方由一个辅助函数来处理，即percdown。
listing 5
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
关于二叉堆的最后一部分便是找到从无序列表生成一个“堆”的方法。我们首先想到的是，将无序列表中的每个元素依次插入到堆中。对于一个排好序的列表，我们可以用二分搜索找到合适的位置，然后在下一个位置插入这个键值到堆中，时间复杂度为o(logn)。另外插入一个元素到列表中需要将列表的一些其他元素移动，为新节点腾出位置，时间复杂度为o(n)。因此用insert方法的总开销是o(nlogn)。其实我们能直接将整个列表生成堆，将总开销控制在o(n)。listing 6 所示的是生成堆的操作。
listing 6
def buildheap(self,alist):
i = len(alist) // 2
self.currentsize = len(alist)
self.heaplist = [0] + alist[:]
while (i > 0):
self.percdown(i)
i = i – 1
i = 2 [0, 9, 5, 6, 2, 3]
i = 1 [0, 9, 2, 6, 5, 3]
i = 0 [0, 2, 3, 6, 5, 9]
下列所示的代码是完全二叉堆的实现。
def insert(self,k):
self.heaplist.append(k)
self.currentsize = self.currentsize + 1
self.percup(self.currentsize)
def percdown(self,i):
while (i * 2) 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
能在o(n)的开销下能生成二叉堆看起来有点不可思议，其证明超出了本书的范围。但是，要理解用o(n)的开销能生成堆的关键是因为logn因子基于树的高度。而对于buildheap里的许多操作，树的高度比logn要小。
以上就是python实现二叉堆的方法的详细内容，更多请关注 第一php社区 其它相关文章！