python3 算法之实现大顶堆

#大顶堆

class PriorityQueue(object):
    heapList=[-1]*100
    writeIndex = 1

    def __init__(self,list):
        self.initByList(list)

    def parent(self,root:int) ->int:
        return  int(root/2)

    def left(self,root:int) -> int:
        return int(root*2)

    def right(self,root:int) -> int:
        return  int(root*2+1)

    def initByList(self,list) -> int:
        for i,val in enumerate(list):
            self.heapList[self.writeIndex] = val
            self.swim(self.writeIndex)
            self.writeIndex+=1
        return  self.writeIndex-1

    # 上浮
    def swim(self,index:int) -> int:
        if index==1:
            return

        pi = self.parent(index)

        if self.heapList[pi]<self.heapList[index]:
            self.heapList[pi],self.heapList[index] = self.heapList[index],self.heapList[pi]
            self.swim(pi)

    # 下沉
    def sink(self,index:int):
        rootVal = self.heapList[index]
        leftVal = self.heapList[index*2]
        rightVal = self.heapList[index*2+1]
        if rootVal>=leftVal and rootVal>= rightVal:
            return
        if (rootVal>leftVal and rootVal<rightVal) or ( rootVal<leftVal and rootVal< rightVal and rightVal>leftVal):
            self.heapList[index],self.heapList[index*2+1] = self.heapList[index*2+1],self.heapList[index]
            self.sink(index*2+1)
        if rootVal>rightVal and rootVal<leftVal or ( rootVal<leftVal and rootVal< rightVal and rightVal<leftVal):
            self.heapList[index], self.heapList[index * 2 ] = self.heapList[index * 2 ], self.heapList[index]
            self.sink(index * 2)


    # 删除最大值
    def delMax(self):
        cindex=  self.writeIndex-1
        self.heapList[1],self.heapList[cindex] = self.heapList[cindex],self.heapList[1]
        self.heapList[cindex] = -1
        self.sink(1)

queue = PriorityQueue([2,10,100,4,9,10,1000,9888,888,999,1,20,89,90,20,70,234,87,190,98,93,96,10,7,9,5,1,2,3,4])



print(queue)

queue.delMax()

print(queue)