Problem:
Priority Queue A priority queue is a data structure which maintains a set $S$ of elements, each of with an associated value (key), and supports the following operations:  $insert(S, k)$: insert an element $k$ into the set $S$  $extractMax(S)$: remove and return the element of $S$ with the largest key  Write a program which performs the $insert(S, k)$ and $extractMax(S)$ operations to a priority queue $S$.
  The priority queue manages a set of integers, which are also keys for the priority. Input Multiple operations to the priority queue $S$ are given. Each operation is given by " insert $k$", " extract " or " end " in a line. Here, $k$ represents an integer element to be inserted to the priority queue. The input ends with " end " operation. Output For each " extract " operation, print the element extracted from the priority queue $S$ in a line. Constraints  The number of operations $\leq 2,000,000$  $0 \leq k \leq 2,000,000,000$  Sample Input 1 insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end Sample Output 1 8
10
11
2

Solution (Python):
import sys
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    i = 0
    while True:
        l = i * 2 + 1
        r = i * 2 + 2
        if l >= n:
            break
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            i = largest
        else:
            break
    return ans
A = [0] * 2000000
S = []
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        S.append(extractMax(A))
    else:
        break
print("\n".join(map(str, S)))

Solution (Python):
import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print("\n".join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:print(-heappop(H))

Solution (Python):
import sys
from heapq import *
H=[]
O=''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=f'{-heappop(H)}\n'
print(O[:-1])

Solution (Python):
import sys
from heapq import *
H=[]
O=''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=f'{-heappop(H)}\n'
print(O[:-1])

Solution (Python):
import sys
from heapq import *
H=[]
O=''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=f'{-heappop(H)}\n'
print(O[:-1])

Solution (Python):
import sys
from heapq import *
H=[]
O=''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=f'{-heappop(H)}\n'
print(O[:-1])

Solution (Python):
import sys
from heapq import *
H=[]
O=''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=f'{-heappop(H)}\n'
print(O[:-1])

Solution (Python):
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 c=e[2]
 if's'==c:heappush(H,-int(e[7:]))
 elif't'==c:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 c=e[2]
 if's'==c:heappush(H,-int(e[7:]))
 elif't'==c:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print("\n".join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print("\n".join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'end'==e:break
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'end'==e:break
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import heappush,heappop
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import heappush,heappop
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import heappush,heappop
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import heapq,sys
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heapq.heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heapq.heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import heapq,sys
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heapq.heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heapq.heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import heapq,sys
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heapq.heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heapq.heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import heapq,sys
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heapq.heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heapq.heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))

Solution (Python):
from heapq import *

a = []
while 1:
    com = input().split()
    if com[0] == 'end':
        break
    elif com[0] == 'insert':
        heappush(a, -int(com[1]))
    else:
        print(-heappop(a))

Solution (Python):
import sys


def run():
    q = []

    for line in sys.stdin:
        if line.startswith("i"):
            v = int(line[7:])
            q.append(v)
            i = len(q) - 1
            while i > 0:
                p = (i-1) // 2
                vp = q[p]
                if vp < v:
                    q[p], q[i] = v, vp
                    i = p
                else:
                    break
        elif line.startswith("ex"):

            size = len(q) - 1
            if size < 0:
                raise ValueError('get from empty queue')

            v = q[0]
            last = q.pop()
            if size > 0:
                q[0] = last
                i = 0
                while i < size // 2:
                    top, vt = i, last
                    left = (i+1) * 2 - 1
                    right = (i+1) * 2
                    if left < size:
                        vl = q[left]
                        if vl > vt:
                            top, vt = left, vl
                    if right < size:
                        vr = q[right]
                        if vr > vt:
                            top, vt = right, vr

                    if top > i:
                        q[top], q[i] = last, vt
                        i = top
                    else:
                        break
            print(v)
        elif line.startswith("end"):
            break
        else:
            ValueError("invalid command")


if __name__ == '__main__':
    run()

Solution (Python):
from heapq import *
a = []
while True:
    s = input()
    if s[2] == "d":break
    elif s[0] == "i":heappush(a, -int(s[7:]))
    else:print(-heappop(a))

Solution (Python):
import sys
from heapq import heappush, heappop


pq = []
lines = sys.stdin.readlines()
for line in lines:
    op = line.strip().split(' ')
    if op[0] == 'insert':
        heappush(pq, -int(op[1]))
    elif op[0] == 'extract':
        print(-heappop(pq))
    else:
        break

Solution (Python):
import heapq

def main():
    q = []
    heapq.heapify(q)
    while True:
        s = input().split()
        if s[0] == 'end':
            break
        elif s[0] == 'insert':
            heapq.heappush(q, -int(s[1]))
        else:
            p = heapq.heappop(q)
            print(-p)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from heapq import *

q = []
while True:
    cmd = sys.stdin.readline().split()
    if cmd[0] == 'end':
        break
    elif cmd[0] == 'insert':
        heappush(q, -int(cmd[1]))
    else:
        print(-heappop(q))

Solution (Python):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import sys
 
def extractMax(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H: 
        v = A[i]
        rv = 0
        lv = 0
        r = (i+1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]
 
        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x
 
def insert(A, n):
    i = len(A)
    A.append(n)
    while i > 0: 
        p = int((i + 1) / 2) - 1
        v = A[i]
        pv = A[p]
        if pv < v: 
            A[p] = v
            A[i] = pv
            i = p
        else:
            break
 
def main():
    """ ????????? """
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
 
    end = False
    S = []
    for cmd in cmds: 

        if cmd[0] == "i":
            insert(S,int(cmd[7:]))
 
        elif cmd == "extract":
            a = extractMax(S)
            print(a)
 
        elif cmd == "end":
            end = True
            break
 
 
if __name__ == '__main__':
    main()

Solution (Python):
import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


if __name__ == '__main__':
    main()

Solution (Python):

from __future__ import division, print_function
from sys import stdin, exit


def max_heapify(a, i):
    heap_size = a[0]

    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)


def main():
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])

            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            print(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            exit(0)


main()

Solution (Python):
import heapq
H = []
heapq.heapify(H)
while True:
    tmp = input().split()
    if tmp[0] == "end":
        break
    if tmp[0] == "insert":
        heapq.heappush(H, -int(tmp[1]))
    elif tmp[0] == "extract":
        ret = heapq.heappop(H)
        print(-ret)

Solution (Python):
import sys
import heapq

readline = sys.stdin.readline


def main():
    _, a = readline().strip().split()
    pq = [-int(a)]
    heapq.heapify(pq)
    flag = True

    while flag:
        op = readline().strip()
        if op[0] == "i":
            _, a = op.split()
            heapq.heappush(pq, -int(a))
        elif op[1] == "x":
            a = heapq.heappop(pq)
            print(-a)
        else:
            flag = False

    return


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappop, heappush, heappushpop

heap = []
while True:
    tmp = input()
    if tmp.startswith('end'):
        break
    elif tmp.startswith('insert'):
        k = int(tmp.split()[1])
        heappush(heap,-k)
    elif tmp.startswith('extract'):
        print(-heappop(heap))

Solution (Python):
import sys
input = sys.stdin.readline

import heapq

A = [] 

while True:
    com = input()
    if com[:2] == 'en':
        break
    if com[0] == 'i':
        _, key = com.split()
        key = -int(key)  
        heapq.heappush(A, key)
    else:
        print(-heapq.heappop(A))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    heap = []
    heapq.heapify(heap)

    while True:
        que = sl()
        if que[0] == 'end':
            break
        elif que[0] == 'insert':
            heapq.heappush(heap, int(que[1]) * (-1))
        elif que[0] == 'extract':
            print(heapq.heappop(heap) * (-1))


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
a = []
command = input().split()

while command[0] != 'end':
    if command[0][0] == 'i':
        heapq.heappush(a, -int(command[1]))
    else:
        print(-heapq.heappop(a))
    command = input().split()

Solution (Python):
import heapq
L = []
heapq.heapify(L)

import sys
for a in sys.stdin:
    if a[0]=='i':
        heapq.heappush(L, -int(a[7:]))
    elif a[0:2]=='ex':
        e = heapq.heappop(L)
        print(-e)
    else:
        break

Solution (Python):
from heapq import *
H = []
heapify(H)
while True:
    scan = input().split()
    if len(scan) == 2:
        heappush(H,-int(scan[-1]))
    else:
        if scan[0] == "end":
            break
        else:
            print(-heappop(H))

Solution (Python):
import heapq
hp=[]
heapq.heapify(hp)
tmp=input()
while True:
    if tmp.startswith("insert"):
        order,number=tmp.split()
        number=int(number)
        heapq.heappush(hp,-number)
    elif tmp.startswith("extract"):
        print(-heapq.heappop(hp))
    elif tmp.startswith("end"):
        break
    tmp=input()

Solution (Python):
import heapq

A = []
heapq.heapify(A)

while True:
    tmp = input()
    if tmp == "end":
        break
    elif tmp[0] == "i":
        heapq.heappush(A, int(tmp[7:])*(-1))
    else:
        print(heapq.heappop(A)*(-1))

Solution (Python):
from heapq import *
a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':heappush(a,-int(b[7:]))
    else:print(-heappop(a))

Solution (Python):
from heapq import heapify, heappush, heappop

def main():
    s = ''
    h = []
    heapify(h)
    for _ in range(2000000):
        s = list(input().split())
        if s[0] == 'end':
            break
        if s[0] == 'insert':
            heappush(h, int(s[1]) * -1)
        if s[0] == 'extract':
            print(heappop(h) * -1)

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heapify, heappop, heappush, heappushpop

heap = []

while True:
    tmp = input()
    if tmp.startswith('end'):
        break
    elif tmp.startswith('insert'):
        k = int(tmp.split()[1])
        heappush(heap, -k)
    elif tmp.startswith('extract'):
        print(-heappop(heap))

Solution (Python):
import sys, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = []
    while True:
        order = LSS()
        if order[0] == 'insert':
            k = int(order[1])
            heapq.heappush(S, -k)
        elif order[0] == 'extract':
            ans = - heapq.heappop(S)
            print(ans)
        else:
            break

if __name__ == '__main__':
    resolve()

Solution (Python):
from heapq import heappop, heappush
import sys

q = []
ans = []
while True:
    s = sys.stdin.readline()
    if s[0] == 'i':
        heappush(q, -int(s[7:]))
    elif s[2] == 't':
        ans.append(-heappop(q))
    else:
        break
print('\n'.join(map(str, ans)))

Solution (Python):
import heapq

Q = []
while True:
    lis = input().split()
    if lis[0] == "insert":
        heapq.heappush(Q, (-1) * int(lis[1]))
    if lis[0] == "extract":
        n = heapq.heappop(Q)
        print(-n)
    if lis[0] == "end":
        break

Solution (Python):

import heapq
Q = []
while True:
    t = input()
    if t == 'end':
        break
    elif t == 'extract':
        n = heapq.heappop(Q)
        print((-1)*n)
    else:
        a,b = t.split()
        heapq.heappush(Q,(-1)*int(b))

Solution (Python):
import heapq as hq
q = []
while True:
    inp = str(input())
    if inp == 'end':
        break
    elif inp == 'extract':
        print(- hq.heappop(q))
    else:
        k = inp[7:]
        hq.heappush(q, - int(k))

Solution (Python):
import heapq
q=[]
heapq.heapify(q)
while True:
    temp = input()
    if temp=="end":
        break    
    if temp=="extract":
        num= heapq.heappop(q)
        print(num*(-1))
    else:
        a,b= temp.split()
        b=int(b)
        heapq.heappush(q,b*(-1))

Solution (Python):
import heapq

def insert(a,key):
    key2=-key
    heapq.heappush(a,key2)

def extract(a):
    key=heapq.heappop(a)
    return -key

a=[]
cmds=input().split()
while(cmds[0] != 'end'):
    if(cmds[0]=='insert'):
        op=int(cmds[1])
        insert(a,op)
    elif(cmds[0]=='extract'):
        print(extract(a))
    cmds=input().split()

Solution (Python):
import heapq
l = []
heapq.heapify(l)
while True:
    o = input().split()
    if o[0].lower() == 'end':
        break
    elif o[0] == 'insert':
        heapq.heappush(l,int(o[1])*-1)
    elif o[0] == 'extract':
        print(heapq.heappop(l)*(-1))

Solution (Python):
from heapq import heapify, heappush, heappop

pq = []
heapify([])
while True:
    S = input()
    if S == "end":
        break
    elif S == "extract":
        print(-1 * heappop(pq))
    else:
        com, k = S.split()
        k = -1 * int(k)
        heappush(pq, k)

Solution (Python):
import heapq
heap = []
while True:
    op = input().split()
    if op[0] == 'end':
        break
    elif op[0] == 'insert':
        heapq.heappush(heap, -int(op[1]))
    elif op[0] == 'extract':
        print(-heapq.heappop(heap))

Solution (Python):
import heapq
q = []
cmd = []
heapq.heapify(q)
while True:
    cmd.clear()
    cmd = input().split()
    if cmd[0] =='insert':
        heapq.heappush(q, -int(cmd[1]))
    elif cmd[0] =='extract':
        p = heapq.heappop(q)
        print(-p)
    elif cmd[0]=='end':
        break;

Solution (Python):
import heapq
heap=[]
from sys import stdin
while(True):
    n = list((stdin.readline().strip().split()))
    if len(n)==2:
        key=int(n[1])
        key*=-1
        heapq.heappush(heap,key)
    else:
        if n[0]=="extract":
            a=heapq.heappop(heap)
            print(a*-1)
        else:
            break

Solution (Python):
import heapq
heap = []
while 1:
    order = input().split()
    if order[0] == "insert":
        k = -int(order[1])
        heapq.heappush(heap,k)
    elif order[0] == "extract":
        print(-heapq.heappop(heap))
    elif order[0] == "end":
        break

Solution (Python):
from heapq import heapify, heappop, heappush
a = []
heapify(a)

while True:
    s = input()
    if s == 'end':
        break
    elif s == 'extract':
        print(-heappop(a))
    else:
        heappush(a, -int(s.split()[1]))

Solution (Python):
from heapq import heappush, heappop

H = []
while True:
    com = input().split()
    if com[0] == 'insert':
        key = int(com[1])
        heappush(H, -key)
    elif com[0] == 'extract':
        print(-heappop(H))
    elif com[0] == 'end':
        break

Solution (Python):
import sys
from heapq import heappush,heapify,heappop
def input(): return sys.stdin.readline().strip()

a = []

while 1:
    
    order = input()
    
    if order == "end":
        exit()
    elif order == "extract":
        b = heappop(a)
        print(-b)

    else:
        order,value = order.split()
        heappush(a,-1*int(value))

Solution (Python):
import heapq

def main():
    pq = []
    heapq.heapify(pq)
    while True:
        com = list(input().split())
        if com[0]=='end':break
        if com[0]=='insert':
            heapq.heappush(pq,-int(com[1]))
        else :
            print(-heapq.heappop(pq))



if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heapify, heappop, heappush
q = []
heapify(q)
b = True
while b:
    li = input().split()
    if li[0] == 'insert':
        li[1] = int(li[1])
        heappush(q, li[1]*(-1))
    elif li[0] == 'extract':
        print(heappop(q)*-1)
    else:
        b = False

Solution (Python):
from heapq import *
q = []
while True:
    s = input().split()
    if s[0] == 'end':
        break
    if s[0] == 'insert':
        heappush(q, -int(s[1]))
    else:
        print(-heappop(q))

Solution (Python):
def resolve():
    '''
    code here
    '''
    import sys
    import heapq
    queries = sys.stdin.readlines()
    
    heap = []

    for line in queries:
        query, *val = line.split()
        
        if query == 'insert':
            value = -1 * int(val[0])
            heapq.heappush(heap, value)
        if query == 'extract':
            print(-1 * heapq.heappop(heap))

    

if __name__ == "__main__":
    resolve()

Solution (Python):

import sys
sys.setrecursionlimit(15000)
n = 0
A = [0]

def maxHeapify(A, i):
  l = i*2
  r = l+1
  if l <= n and A[l] > A[i]:
    largest = l
  else:
    largest = i
  if r <= n and A[r] > A[largest]:
    largest = r
  if largest != i:
    A[i],A[largest]=A[largest],A[i]
    maxHeapify(A,largest)

def insert(k):
  A.append(k)
  global n
  n += 1
  i = n
  while i > 1:
    
    p = i>>1
    if A[p] > A[i]:
      break
    A[p],A[i] = A[i],A[p]
    i = p
  
  

def extract():
  ret = A[1]
  global n
  if 1 < n:
    A[1] = A.pop()
  else:
    A.pop()
  n -= 1
  maxHeapify(A,1)
  
  return ret

S = sys.stdin.readlines()
o = []
for s in S:

  if s[2]=="d":
    
    print(*o,sep='\n')
    exit(0)
  elif s[0] == "i":
    insert(int(s[7:]))
  else:
    o.append(extract())

Solution (Python):
from heapq import heappush, heappop
import sys

que = []
ans = []
for line in sys.stdin.readlines():
    cmd, *v = line.split()
    if cmd == 'insert':
        heappush(que, -int(v[0]))
    elif cmd == 'extract':
        ans.append("%d\n" % -heappop(que))
sys.stdout.writelines(ans)

Solution (Python):
from heapq import *
import sys

q = []
while True:
  
  commands=sys.stdin.readline().split()

  if commands[0] == "end":
    break

  if commands[0] == "insert":
    heappush(q, -int(commands[1]))
  else:
    print(-heappop(q))

Solution (Python):
a = []
import heapq  

heapq.heapify(a)  

while True:
    cm = input()
    if cm=='end':
        break
    elif cm.split()[0]=='insert':
        heapq.heappush(a, int(cm.split()[1])*(-1)) 
    elif cm.split()[0]=='extract':
        print(heapq.heappop(a)*(-1))

Solution (Python):
from heapq import heappush, heappop

heap = []
while True:
    n = input().split()
    if n[0] == 'end':
        break
    elif n[0] == 'insert':
        heappush(heap, -int(n[1]))
    else:
        print(-heappop(heap))

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    import heapq

    H = 0
    MAX = 2000000
    A = []

    while True:
        com = input()
        if com[:2] == 'en':
            break
        if com[0] == 'i':
            _, key = com.split()
            key = -int(key)  
            heapq.heappush(A, key)
        else:
            print(-heapq.heappop(A))

Solution (Python):
import heapq

S = []

heapq.heapify(S)

while True:
  l = input().split()
  if len(l) == 2:
    heapq.heappush(S, (-1)*int(l[1]))
  elif l[0] == "extract":
    print(heapq.heappop(S)*(-1))
  else:
    break

Solution (Python):
import sys
print = sys.stdout.write

def insert(key, queue):
    """priority queueに値を代入する.
    
    Args:
        key (int): priority queueに代入する数値.

    Notes:
        indexは扱いやすさのため1~nを想定してしている.
        配列値取得時にはpythonの仕様に合わせて-1としている.
    """
    queue.append(key)
    index = n
    if index == 1:
        return
    parent_index = index//2
    while parent_index and queue[parent_index-1] < key:
        queue[index-1] = queue[parent_index-1]
        index, parent_index = parent_index, parent_index//2
    queue[index-1] = key
    
def extract_max(queue):
    index = 1
    root = queue[0]
    l_index = index*2
    num = n
    while l_index < num:
        ql, qr = queue[l_index-1], queue[l_index]
        bigger = (l_index, ql) if ql > qr else (l_index+1, qr)
        if bigger[1] > root:
            next_index = bigger[0]
            queue[index-1] = queue[next_index-1]
            index = next_index
            l_index = index*2
        else:
            break
        
    if l_index == num:
        if queue[l_index-1] > root:
            queue[index-1] = queue[l_index-1]
            index = l_index
    queue[index-1] = root


def main():
    S = []
    global n
    n = 0
    for operation in sys.stdin.readlines():
        if operation[0] == "i":
            n += 1
            insert(int(operation[7:]), S)
        elif operation[1] == "x":
            print("{}\n".format(S[0]))
            S[0] = S.pop()
            n -= 1
            extract_max(S)
        elif operation == "end":
            break

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappop, heappush, heappushpop

heap = []

while True:
    tmp = input()
    if tmp.startswith('end'):
        break
    elif tmp.startswith('insert'):
        k = int(tmp.split()[1])
        heappush(heap, -k)
    elif tmp.startswith('extract'):
        print(-heappop(heap))

Solution (Python):
import heapq
d = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    if s[0] == "insert":
        heapq.heappush(d, -int(s[1]))
    if s[0] == "extract":
        c = heapq.heappop(d)
        print(-c)