二叉堆
1 基于二叉堆的优先队列
在优先级队列中，队列中的项的逻辑顺序由它们的优先级确定。最高优先级项在队列的前面，最低优先级的项在后面。因此，当你将项排入优先级队列时，新项可能会一直移动到前面。
我们只使用一个单一的列表作为二叉堆的内部表示。
二叉堆有两个常见的变体：最小堆（其中最小的键总是在前面）和最大堆（其中最大的键值总是在前面）。
我们将实现最小堆。
2 二叉堆实现
利用二叉树的对数性质来表示我们的堆。
2.1 完整二叉树
一个完整的二叉树是一个树，其中每个层都有其所有的节点，除了树的最底层，从左到右填充。
2.2 堆的属性
可以使用单个列表来表示它。
父节点的左子节点（在位置 p 处） 是在列表中位置 2p 中找到的节点。 类似地，父节点的右子节点在列表中的位置 2p + 1。为了找到树中任意节点的父节点，我们可以简单地使用 Python 的整数除法。
堆的排序属性如下：在堆中，对于具有父 p 的每个节点 x，p 中的键小于或等于 x 中的键。
2.3 堆操作
2.3.1 init 函数
一个空的二叉堆有一个单一的零作为 heapList 的第一个元素，这个零只是放那里，用于以后简单的整数除法。
def __init__(self): self.heapList = [0] self.currentSize = 0
2.3.2 insert 函数
将项添加到列表中最简单，最有效的方法是将项附加到列表的末尾。 它维护完整的树属性。但可能违反堆结构属性。可以编写一个方法，通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 如果新添加的项小于其父项，则我们可以将项与其父项交换。
下图展示了将新添加的项替换到其在树中的适当位置所需的操作。
当添加完一个新项后，需要对二叉堆进行维护，由 perUp 函数接管，它在树中向上遍历一个新项并正确定位该新项。
def perUp(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 insert(self, k): self.heapList.append(k) self.currentSize += 1 self.perUp(self.currentSize)
2.3.3 delMin 函数
堆属性要求树的根是树中的最小项，所以找到最小项很容易。
难点在根被删除后恢复堆结构和堆顺序属性。
- 通过获取列表中的最后一个项并将其移动到根位置来恢复根项。
- 通过将新的根节点沿着树向下推到其正确位置来恢复堆顺序属性。
为了维护堆顺序属性，我们所需要做的是将根节点和最小的子节点交换。
将节点和其子节点重复交换，直到节点被交换到正确的位置，使它小于两个子节点。
percDown 和 minChild 方法实现树交换节点。percDown 方法确保最大的子节点总是沿着树向下移动。
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 + 1def perDown(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
delMin 函数的代码。
def delMin(self): retval = self.heapList[1] self.heapList[1] = self.heapList[self.currentSize] self.currentSize = self.currentSize - 1 self.heapList.pop() self.perDown(1) return retval
2.3.4 buildHeap 函数
buildHeap 函数用于构建整个堆。
def buildHeap(self, alist): i = len(alist) // 2 self.currentSize = len(alist) self.heapList = [0] + alist[:] while i > 0: self.perDown(i) i = i - 1
2.4 完整代码
class BinHeap(object): def __init__(self): self.heapList = [0] self.currentSize = 0 def perUp(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 insert(self, k): self.heapList.append(k) self.currentSize += 1 self.perUp(self.currentSize) 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 perDown(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 delMin(self): retval = self.heapList[1] self.heapList[1] = self.heapList[self.currentSize] self.currentSize = self.currentSize - 1 self.heapList.pop() self.perDown(1) return retval def buildHeap(self, alist): i = len(alist) // 2 self.currentSize = len(alist) self.heapList = [0] + alist[:] while i > 0: self.perDown(i) i = i - 1if __name__ == '__main__': bh = BinHeap() bh.buildHeap([9, 5, 6, 2, 3]) print(bh.delMin()) print(bh.delMin()) print(bh.delMin()) print(bh.delMin()) print(bh.delMin())
