题解 | #【模板】堆#

class Heap:
    def __init__(self) -> None:
        self.a = [0]    # 让下标从1开始，方便计算，该数不为堆中元素
        self.size = 0   # 堆元素数量

    def push(self, x):
        self.a.append(x)
        self.size += 1
        k = self.size
        while k > 1 and self.a[k//2] < self.a[k]:
            self.a[k//2], self.a[k] = self.a[k], self.a[k//2]
            k = k//2
        
    def top(self):
        if self.size == 0:
            return 'empty'
        return self.a[1]

    def pop(self):
        if self.size == 0:
            return 'empty'
        top = self.a[1]
        self.a[1] = self.a[-1]
        self.a.pop()
        self.size -= 1
        
        k = 1
        while 2*k <= self.size:
            j = 2*k
            if j < self.size and self.a[j] < self.a[j+1]:
                j += 1
            if self.a[k] >= self.a[j]:
                break
            self.a[k], self.a[j] = self.a[j], self.a[k]
            k = j
        return top


n = int(input())
hp = Heap()
for i in range(n):
    line = input().split()
    if line[0] == 'push':
        hp.push(int(line[1]))
    elif line[0] == 'top':
        print(hp.top())
    elif line[0] == 'pop':
        print(hp.pop())