最大堆实现，python

################堆 heap
class MaxHeap: #索引0不用&＃xff0c;所以数组大小应该是 n&＃43;1##左节点2i 右节点2i&＃43;1,父节点 i/2def __init__(self):self._data&＃61; [] #堆数组容量不知道self._count&＃61;len(self._data)def size(self):return self._countdef isEmpty(self):return self._count&＃61;&＃61;0def add(self,item):##添加assert self._count&＃43;1<&＃61;capacity,"超出数组容量"##可加可不加self._data.append(item)self._count&＃43;&＃61;1self._shiftup(self._count)#上移&＃xff0c;传递最后一个索引def _shiftup(self,index):##索引要考虑索引越界&＃xff0c;所以边界什么情况# 添加元素&＃xff0c;然后上移元素&＃xff0c;满足不大于父元素的特性parent&＃61;(index)/2 #父节点索引大于等于1,所以index 最小2while (index>1 and self._data[parent])0ret &＃61; self._data[0]self._data[0]&＃61;self._data[self._count]#最后一个值填充到第一个位置self._count&＃61;self._count-1self._shiftdown(1) #下移传递第一个索引return retdef _shiftdown(self,index):#先判断是否有子节点&＃xff0c;完全二叉树&＃xff0c;不可能右节点&＃xff0c;没有左节点while (2*index<&＃61;self._count): #循环判断当前节点的左节点是否存在&＃xff0c;如果不存在已经比较结束了#先找到左右子树的最大值是哪个j &＃61; 2*indexif j&＃43;1 <&＃61;self._count and self._data[j&＃43;1]>self._data[j]:j&＃61;j&＃43;1if self._data[index]>&＃61;self._data[j]break#交换&＃xff0c;如果分行写需要中间变量&＃xff0c;这样写可以直接交换self._data[index], self._data[j] &＃61; self._data[j], self._data[index]self._data[index]index&＃61;j #索引跟随值移动&＃xff0c;往下