最大堆实现，python

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