Envío 6362

Código

from functools import total_ordering

@total_ordering
class Node:
    def __init__(self, s, p):
        self.s = s
        self.p = -p

    def __lt__(self, other):
        if self.p < other.p:
            return True
        elif self.p > other.p:
            return False
        return self.s < other.s
    
    def __eq__(self, other):
        return self.s == other.s and self.p == other.p

    def __repr__(self):
        return f"{self.s}"

class Heap:
    def __init__(self):
        self.tree = []

    def right(self, i):
        return (i << 1) + 1

    def left(self, i):
        return (i << 1) + 2

    def parent(self, i):
        return (i - 1) >> 1

    def __len__(self):
        return len(self.tree)

    def heapify_down(self, i):
        l = self.left(i)
        r = self.right(i)
        children = [c for c in [l, r] if c < len(self.tree)]
        #print(i, children, self.tree)
        if all(self.tree[i] < self.tree[c] for c in children):
            return     
        sm = min(children, key = lambda x: self.tree[x])
        self.tree[sm], self.tree[i] = self.tree[i], self.tree[sm]
        self.heapify_down(sm)

    def heapify_up(self, i):
        while i != 0:
            p = self.parent(i)
            #print(f"{i=} {p=}")
            if self.tree[p] <= self.tree[i]:
                break    
            self.tree[p], self.tree[i] = self.tree[i], self.tree[p]
            i = p

    def add(self, elem):
        self.tree.append(elem)
        self.heapify_up(len(self.tree) - 1)


    def pop(self): 
        self.tree[-1], self.tree[0] = self.tree[0], self.tree[-1]
        res = self.tree.pop()
        self.heapify_down(0)
        return res

    def peek(self):
        return self.tree[0]

    def __repr__(self):
        return f"{self.tree}"    

h = Heap()
num_lines = int(input())
for _ in range(num_lines):
    line = input()
    if line[0] == "I":
        _, s, p = line.split(" ")
        n = Node(s, int(p))
        h.add(n)
    elif line[0] == "G":
        n = h.peek()
        print(n)
    else:
        h.pop()