题解 | 【模板】堆

通过完全二叉树构建堆：（索引为 i的节点，左子树和右子树分别是2i+1和2i+2）

1.push 的时候，将元素加入到末尾，通过_heapify_up 进行调整（和父节点比较大小）

2.pop 的时候，交换堆顶元素和末尾元素，通过_heapify_down 进行调整（和左右子树比较大小）

class Heap:
    def __init__(self):
        self.heap=[]
    
    def _heapify_up(self):
        #末尾元素向上调整，只需要不断和父节点进行比较就行
        #考虑2i+1, 2i+2 -> i，父节点的索引是 (index-1)//2
        idx=  len(self.heap)-1
        while idx:#向上调整，直到idx=0也就是堆顶
            parent_idx=(idx-1)//2
            if self.heap[parent_idx]<self.heap[idx]:
                self.heap[parent_idx],self.heap[idx]=  self.heap[idx],self.heap[parent_idx]
                idx=parent_idx
                continue
            break #说明self.heap[parent_idx]>=self.heap[idx]

    def _heapify_down(self):
        #堆顶元素向下调整，只需要不断和左、右子树进行比较就行
        i=0
        n=len(self.heap)
        while 2*i+1<n:
            left=2*i+1
            right=2*i+2
            if self.heap[left]<=self.heap[i]:#左子树小于等于根，可能无需调整，看下右子树是否存在且大于根
                if right<n and self.heap[right]>self.heap[i]:
                    self.heap[i],self.heap[right]=self.heap[right], self.heap[i]
                    i=right
                else:#无需调整，则提前结束循环
                    break
            else:#左子树大于根，则必然需要调整，只是还需要看右子树是否存在且大于左子树
                if right<n and self.heap[right]>self.heap[left]:
                    self.heap[i],self.heap[right]=self.heap[right], self.heap[i]
                    i=right
                else:
                    self.heap[i],self.heap[left]=self.heap[left], self.heap[i]
                    i=left

    def push(self,x):#入堆之后，需要进行调整
        self.heap.append(x)
        self._heapify_up()
    
    def pop(self):#弹出堆顶元素之后，需要进行调整
        print(self.heap[0])
        #adjust：先交换堆顶元素和最末尾的元素，弹出末尾元素
        self.heap[0],self.heap[-1]=self.heap[-1], self.heap[0]
        self.heap.pop()
        self._heapify_down()

    def top(self):
        print(self.heap[0])


n=int(input())
h=Heap()
for _ in range(n):
    op=input().split()
    if op[0]=='push':
        h.push(int(op[1]))
    elif not h.heap:#堆为空的情况下，直接输出"empty"
        print('empty')
    elif op[0]=='top':
        h.top()
    else: #op[0]=='pop':
        h.pop()