python的堆模块，heapq，默认为小根堆，操作：
heapq.heappush(heap,x) #把x压入堆
heapq.heappop(heap)
heapq.heapreplace(heap,x) #删除最小根，然后压入x
heapq.heapify([2,5,1]) #让列表具有堆特征
用heapq实现大根堆时，入堆和出堆操作，变换为push(-e), -pop(e) .
from pythonds.trees import BinaryHeap堆heap,可以看做一个完全二叉树的数组对象。常见的堆有二叉堆和斐波那契堆。二叉堆的变体中，根据根节点的最大和最小分为最大堆和最小堆。我们用来存储堆元素的方法依赖堆的有序性：对于堆中任意元素x，x及其父元素p，总是有p<=x。完全二叉树: 除了底层，其他层的节点都是满的。在最底层，从左往右填充节点。实现优先级队列的经典方法是二叉堆，即一棵用列表来表达的二叉树。父节点下标为i，子节点的下标为2*i，2*i+1。节点m的父节点为m/2。优先级队列的插入和删除。插入：先插入到列表最后，然后上浮。删除：最后一个元素调换到根节点，将其下沉。
二叉堆的操作7个
BinaryHeap() #创建空的二叉堆
BuildHeap(list) 根据列表创建二叉堆
insert(k) 插入元素
findMin() 返回最小值
delMin() 返回最小值并删除根节点
isEmpty() 判断堆是否为空
size() 返回堆的元素个数
创建空的二叉堆
class BinaryHeap: def __ini__(self): self.heapList=[0] self.currentsize=0
insert(k)
def insert(self): self.heapList.append(k) self.currentsize+=1 self.percUp(self.currentsize)def percUp(self,i): while i//2>0: if self.heapList[i]
delMin()。问题：移除根节点之后，怎么重建堆的有序性和结构性质。1.把最后一个元素移到根节点，保证结构性质。2.元素下沉，保证有序性。
def delMin(self): re=self.heapList[1] self.heapList[1]=self.heapList[self.currentsize] self.currentsize-=1 self.heapList.pop() self.percDown(1) return redef percDown(self,i): while i*2<=self.currentsize m=minChild(i) if self.heapList[m]
BuildHeap(list) 根据已有的列表创建二叉堆,时间复杂度为O（n）。从倒数第二层的节点开始，每个节点依次下沉，i-=1。
def BuildHeap(self,alist): self.heapList=[0]+alist[:] self.currentsize=len(alist) i=len(alist)//2 while i>0: self.percDown(i) i=i-1