题解 | #【模板】堆#

class MaxHeap():
    def __init__(self):
        self.heap = []
    
    def push(self, x):
        self.heap.append(x)
        self._sift_up(len(self.heap) - 1)
    
    def top(self):
        if len(self.heap) == 0:
            return 'empty'
        return self.heap[0]
    
    def pop(self):
        if len(self.heap) == 0:
            return 'empty'
        #将下层元素上浮到合适位置
        max_val = self.heap[0]
        last_val = self.heap.pop()
        
        if len(self.heap) > 0:
            self.heap[0] = last_val
            self._sift_down(0)
        
        return max_val
    #从给定位置向上移动元素,将给定索引i的元素与其父节点进行比较。如果当前元素大于其父节点，就交换它们的位置，使得当前元素上浮到更高的层级
    def _sift_up(self, i):
        while i > 0 and self.heap[i] > self.heap[(i - 1) // 2]:
            self.heap[i], self.heap[(i - 1) // 2] = self.heap[(i - 1) // 2], self.heap[i]
            #根据堆的完全二叉树特性,i的父节点索引值为(i - 1) // 2，向下取整
            i = (i - 1) // 2
    #从给定位置向下移动元素
    def _sift_down(self, i):
        max_idx = i
        #根据堆的完全二叉树特性，索引为i的节点的左子节点的索引是(2i + 1)
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < len(self.heap) and self.heap[left] > self.heap[max_idx]:
            max_idx = left
        
        if right < len(self.heap) and self.heap[right] > self.heap[max_idx]:
            max_idx = right
        
        if max_idx != i:
            self.heap[i], self.heap[max_idx] = self.heap[max_idx], self.heap[i]
            self._sift_down(max_idx)


n=input()
myheap=MaxHeap()
for i in range(int(n)):
    a=input().split()
    if a[0]=='push':
        myheap.push(int(a[1]))
    elif a[0]=='top':
         print(myheap.top()  )
    else:
        print(myheap.pop() )