Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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



Sample input:
insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end


Sample output:
8
10
11
2

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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

# import sys, time
#
# class PriorityQueue:
#     __slots__ = ['nodes', 'num']
#
#     def __init__(self):
#         self.nodes = []
#         self.num = 0
#
#     def max_heapify(self, i):
#         if i >= self.num: return
#         left, right = (i+1)*2-1, (i+1)*2
#
#         largest = i
#         if left < self.num and self.nodes[i] < self.nodes[left]: largest = left
#         if right < self.num and self.nodes[largest] < self.nodes[right]: largest = right
#
#         if largest != i:
#             self.nodes[i], self.nodes[largest] = self.nodes[largest], self.nodes[i]
#             self.max_heapify(largest)
#
#     def extract_max(self):
#         if self.num < 1: return
#         max = self.nodes[0]
#         self.nodes[0] = self.nodes[-1]
#         self.nodes.pop()
#         self.num -= 1
#         self.max_heapify(0)
#         return max
#
#     def insert(self, key):
#         self.nodes.append(key)
#         self.num += 1
#         i = self.num-1
#         par = lambda i: (i-1)//2
#         while i > 0 and self.nodes[par(i)] < self.nodes[i]:
#             self.nodes[i], self.nodes[par(i)] = self.nodes[par(i)], self.nodes[i]
#             i = par(i)
#
#     def print_element(self):
#         for node in self.nodes:
#             print('', node, end='')
#         print('')
#
# pq = PriorityQueue()
#
# start = time.time()
# lines = sys.stdin.readlines()
# for line in lines:
#     op = line.strip().split(' ')
#     if op[0] == 'insert':
#         pq.insert(int(op[1]))
#     elif op[0] == 'extract':
#         # print(pq.extract_max())
#         pq.extract_max()
#     else:
#         break
# print('elapsed:', time.time()-start)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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))

Submission status: Accepted

Solution code:
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: # input()
#        print("cmd:{} S:{}".format(cmd,S))
        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()

Submission status: Accepted

Solution code:
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:  # input()
        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()

Submission status: Accepted

Solution code:
#!/usr/bin/env 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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import heapq

A = [] # heapの初期値はリストで持たせておく

while True:
    com = input()
    if com[:2] == 'en':
        break
    if com[0] == 'i':
        _, key = com.split()
        key = -int(key)  # min-ヒープになるので、-1をかけることで解決する。
        heapq.heappush(A, key)
    else:
        print(-heapq.heappop(A)) # 出力するときも-1かけるのを忘れずに

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
# )が１個抜けていた
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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;

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

    # print(heap)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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:
    #print(A)
    p = i>>1
    if A[p] > A[i]:
      break
    A[p],A[i] = A[i],A[p]
    i = p
  #buildMaxHeap(A)
  #maxHeapify(A, n)

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

S = sys.stdin.readlines()
o = []
for s in S:
#while 1:
  if s[2]=="d":
    #print("\n".join(map(str,o)))
    print(*o,sep='\n')
    exit(0)
  elif s[0] == "i":
    insert(int(s[7:]))
  else:
    o.append(extract())
    #print(s,A)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from heapq import *
import sys

q = []
while True:
  # commands = list(map(str, input().split()))
  commands=sys.stdin.readline().split()

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

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

Submission status: Accepted

Solution code:
a = []
import heapq  # heapqライブラリのimport

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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)  # min-ヒープになるので、-1をかけることで解決する。
            heapq.heappush(A, key)
        else:
            print(-heapq.heappop(A))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import heapq

def main():
    l = list()

    while True:
        com, *para = input().split()

        if com == "insert":
            heapq.heappush(l, -int(para[0]))
        elif com == "extract":
            print(-heapq.heappop(l))
        elif com == "end":
            break

main()

Submission status: Accepted

Solution code:
# ライブラリのインポート
#import re #正規表現
#import sys
import heapq
#import collections


def main():
    tempheap = []
    while(1):
        instr = input()
        if instr[2] == 'd': break
        if instr[0] == 'i': heapq.heappush(tempheap, -int(instr[7:]))
        else: 
            print(-heapq.heappop(tempheap))

    


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, heapq
def main():
    input = sys.stdin.readline
    que = []
    ans = []
    while True:
        a = input()
        if a[0] == "i":
            heapq.heappush(que, -int(a[7:]))
        elif a[2] == "t":
            ans.append(-heapq.heappop(que))
        else:
            break
    print("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

a = []
heapq.heapify(a)

while True:
    x = input()
    if x == "end":
        break
    elif x == "extract":
        print(-heapq.heappop(a))
    else:
        p, q = x.split()
        heapq.heappush(a, -int(q))

Submission status: Accepted

Solution code:
"""
ALDS1_9_C
優先度つきキューを実装する
"""
import heapq

List = []
while True:
    order = input().split()
    if order[0][0] == 'i':
        x = int(order[1])
        heapq.heappush(List, -x)
    elif order[0][1] == 'x':
        ans = heapq.heappop(List)
        print(-ans)
    else:
        break

Submission status: Accepted

Solution code:
import sys
import heapq

# 自前の実装だと時間超過になったので、標準ライブラリの heapq を使う。

h = []
while True:
    command, *key = sys.stdin.readline().split()
    if command[0] == 'i': # insert k
        heapq.heappush(h, -int(key[0]))
    elif command[1] == 'x':   # extract
        print(-heapq.heappop(h))
    else:   # end
        break

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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)*(-1)) # 最大のキー（最大値）を取り出す

Submission status: Accepted

Solution code:
from heapq import *
A=[]
while 1:
    queue=input()
    if queue=="end":break
    elif queue[0]=="e":print(-heappop(A))
    elif queue[0]=="i":heappush(A,-int(queue.split()[1]))