题解 | #【模板】堆#

class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, x):
        self.heap.append(x)  # 将元素添加到末尾
        self._heapify_up(len(self.heap) - 1)  # 上浮调整，父节点的值小于当前节点的值则交换

    def top(self):
        if self.heap:  # 直接返回数组的第一个元素（即根节点）
            return self.heap[0]
        else:
            return "empty"

    def pop(self):
        if len(self.heap) == 0:
            return "empty"
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()  # 用列表最后一个元素替换堆顶
        self._heapify_down(0)  # 下沉调整，如果当前节点小于最大的子节点，交换它们的位置。
        return root

    def _heapify_up(self, index):
        parent = (index - 1) // 2
        while index > 0 and self.heap[index] > self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2

    def _heapify_down(self, index):
        size = len(self.heap)
        while True:
            left = 2 * index + 1
            right = 2 * index + 2
            largest = index

            if left < size and self.heap[left] > self.heap[largest]:
                largest = left
            if right < size and self.heap[right] > self.heap[largest]:
                largest = right

            if largest == index:
                break

            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            index = largest


# 测试代码
n = int(input())
heap = MaxHeap()

for _ in range(n):
    command = input().split()

    if command[0] == "push":
        heap.push(int(command[1]))
    elif command[0] == "top":
        print(heap.top())
    elif command[0] == "pop":
        print(heap.pop())