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

Solution (Python):



import heapq



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

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

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

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

Solution (Python):
import sys
import heapq



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

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

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

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


def main():
    heap = []
    while True:
        operation = input()
        if operation[0] == "i":
            heappush(heap, -int(operation.split()[1]))
        elif operation[1] == "x":
            print(-heappop(heap))
        else:
            break


if __name__ == "__main__":
    main()

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

hq=[]
while True:
	s=input()
	if s[0]=="e" and s[1]=="n":
		exit()
	elif s[0]=="e":
		print(-heapq.heappop(hq))
	else:
		q,w=s.split()
		w=int(w)
		heapq.heappush(hq,-w)

Solution (Python):
import heapq
S = []
Q = open(0).read().split()
i = 0
while True:
    it = Q[i]
    if it == 'end':
        break
    elif it == 'insert':
        num = int(Q[i + 1])
        heapq.heappush(S, -num)
        i += 2
    elif it == 'extract':
        ret = heapq.heappop(S)
        print(-ret)
        i += 1

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*

s=""
hq=[]

while s!="end":
    s=input()
    if s=="end":
        break
    if s[0]=="i":
        a,b=s.split()
        heappush(hq,-int(b))
    else:
        print(-heappop(hq))

Solution (Python):
import heapq
queue=[]
heapq.heapify(queue)
while True:
    order=input().split()
    if order[0][0]=='i':
        heapq.heappush(queue,-1*int(order[1]))
    elif order[0][1]=='x':
        print(heapq.heappop(queue)*(-1))
    else:break

Solution (Python):
import sys
nodes = ['OFFSET'] + [-1] * 4000000
_num_nodes = 0
outputs = [None] * 2000000
_num_outputs = 0

def max_heapify(idx):
    left_idx = idx * 2
    right_idx = left_idx + 1

    max_idx = idx

    if nodes[left_idx] > nodes[max_idx]:
        max_idx = left_idx
    if nodes[right_idx] > nodes[max_idx]:
        max_idx = right_idx

    if max_idx != idx:
        tmp = nodes[idx]
        nodes[idx] = nodes[max_idx]
        nodes[max_idx] = tmp
        max_heapify(max_idx)
    return


def insert(node_no):
    global _num_nodes
    nodes[_num_nodes+1] = node_no
    _num_nodes += 1
    idx = _num_nodes
    while idx > 1:
        parent_idx = idx // 2
        if nodes[idx] > nodes[parent_idx]:
            tmp = nodes[parent_idx]
            nodes[parent_idx] = nodes[idx]
            nodes[idx] = tmp
        else:
            break
        idx = parent_idx
    return


def extract():
    global _num_outputs
    outputs[_num_outputs] = nodes[1]
    _num_outputs += 1
    global _num_nodes
    nodes[1] = nodes[_num_nodes]
    nodes[_num_nodes] = -1
    _num_nodes -= 1
    max_heapify(1)
    return


def main():
    commands = sys.stdin.readlines()
    for command in commands:
        if command[0] == 'i':
            insert(int(command[7:]))
        elif command[1] == 'x':
            extract()
        elif command[1] == 'n':
            break

    for i in range(_num_outputs):
        print(outputs[i])
    return


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
def input():
    return sys.stdin.readline()[:-1]

import heapq

def insert(S, v):
    heapq.heappush(S, -v)

def extract(S):
    return -heapq.heappop(S)

S = []
while True:
    args = input().split()
    if args[0] == 'end':
        break
    elif args[0] == 'insert':
        insert(S, int(args[1]))
    else:
        print(extract(S))

Solution (Python):
from heapq import heappush, heappop

if __name__ == "__main__":
	h = []
	while True:
		command = input().split()
		if command[0] == "insert":
			heappush(h, int(command[1]) * -1)
		elif command[0] == "extract":
			print(heappop(h) * -1)
		else:
			break

Solution (Python):

import heapq
H=[]

while True:
    cmmd = input().split()
    if cmmd[0] == "insert":
        heapq.heappush(H,-int(cmmd[1]))
        
    elif cmmd[0] == "extract":
        ext = heapq.heappop(H)
        print(-ext)
    else:
        break

Solution (Python):



from collections import Counter,deque


from sys import stdin,setrecursionlimit

import heapq


setrecursionlimit(10**6)
input=stdin.readline

s=[]
heapq.heapify(s)

while 1:
    c,*n=input().split()
    if c=="end":
        break
    elif c=="insert":
        k=int(n[0])
        heapq.heappush(s,-k)
    else:
        print(-heapq.heappop(s))

Solution (Python):
import heapq


def main():
    S = []
    while True:
        cmd, *v = input().split()
        if cmd == "insert":
            heapq.heappush(S, (-1) * int(v[0]))
            pass
        elif cmd == "extract":
            print(heapq.heappop(S) * (-1))
        else:
            exit()


if __name__ == '__main__':
    main()

Solution (Python):
import heapq


def main():
    heap = []
    while True:
        order = input().split()
        if order[0] == 'insert':
            heapq.heappush(heap, -int(order[1]))
        elif order[0] == 'extract':
            print(-heapq.heappop(heap))
        elif order[0] == 'end':
            return


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
h = []
while True:
    cmd = input().split()
    if cmd[0] == "insert":
        num = int(cmd[1]) * (-1)
        heapq.heappush(h, num)
    elif cmd[0] == "extract":
        num=heapq.heappop(h) * (-1)
        print(num)
    else:
        break

Solution (Python):
from heapq import heappush, heappop
from typing import List


if __name__ == "__main__":
    heap: List[int] = []

    while True:
        op, *value = input().split()
        if "end" == op:
            break
        if "insert" == op:
            heappush(heap, - int(value[0]))
        else:
            print(- heappop(heap))

Solution (Python):
import heapq


heap = []
heapq.heapify(heap)

orders = []
order = input()
while order != "end":
    orders.append(order)
    order = input()

for order in orders:
    if order.startswith("insert"):
        o, x = order.split()
        x = int(x)
        heapq.heappush(heap, -x)
    else:
        print(-heapq.heappop(heap))

Solution (Python):
from heapq import heappush, heappop


heap = []

while True:

    line = input().split()

    if   line[0] == "insert":
        heappush(heap, -int(line[1]))
    elif line[0] == "extract":
        print(-heappop(heap))
    else:
        break

Solution (Python):
import heapq

A = []
heapq.heapify(A)

while True:
    arr = input().split()

    if arr[0] == 'end':
        break

    if arr[0] == 'insert':
        key = int(arr[1]) * -1
        heapq.heappush(A, key)

    if arr[0] == 'extract':
        max = heapq.heappop(A) * -1
        print(max)

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

heap = []

while 1:
    cmd = input().split()

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(-heappop(heap))
    else:
        heappush(heap, -int(cmd[1]))

Solution (Python):
import heapq
Q = []
while True:
    a = input()
    if a == 'end':
        break
    elif a == 'extract':
        t = heapq.heappop(Q)
        print(-t)
    else:
        heapq.heappush(Q,-int(a[7:]))

Solution (Python):
import heapq

S = []
while True:
    op = input()
    if op[:2] == "in":
        op, k = op.split()
        k = int(k)*(-1)
        heapq.heappush(S, k)

    elif op[:2] == "ex":
        print(heapq.heappop(S)*(-1))
    else:
        break

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

input = sys.stdin.readline
pq = []
while True:
    command = list(map(str, input().split()))
    if command[0] == 'insert':
        heappush(pq, int(command[1])*(-1))
    elif command[0] == 'extract':
        print(heappop(pq)*(-1))
    else:
        break

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

Solution (Python):
import heapq

dic = []

while True:
    line = input()
    if line[2] == "d":
        break
    elif line[2] == "t":
        item = heapq.heappop(dic)
        print(-item)
    else:
        value = int(line.split(" ")[1])
        heapq.heappush(dic, -1*int(value))

Solution (Python):
import heapq
import sys
hq = []
while True:
    a = sys.stdin.readline().split()
    if a[0] == 'end':
        break
    if a[0] == 'insert':
        heapq.heappush(hq, -int(a[1]))
    if a[0] == 'extract':
        print(-heapq.heappop(hq))

Solution (Python):
import heapq

A = []
while True:
    line = input().rstrip().split()
    if line[0] == "end":
        break
    elif line[0] == "insert":
        heapq.heappush(A, -int(line[1]))
    else:
        print(-heapq.heappop(A))

Solution (Python):
import heapq
A = []
data_i = []
while True:
    tmp = input()
    if tmp == 'end':
        break
    data_i.append(tmp)




for i in data_i:
    if i[0] == 'i':
        heapq.heappush(A, int(i[7:])*-1)
    else:
        print(heapq.heappop(A)*-1)
    '''
    print(i)
    print(A)
    '''

Solution (Python):
from heapq import heappush, heappop


p_que = []
while True:
    line = input().split()
    if line[0] == 'end':
        break
    elif line[0] == 'insert':
        val = int(line[1])
        heappush(p_que, -val)
    elif line[0] == 'extract':
        print(-1 * heappop(p_que))
    else:
        raise ValueError('想定外の事態')

Solution (Python):





import sys
input = sys.stdin.readline
import heapq


def main():
    tl = []
    while True:
        l  = list(map(str,input().split()))
        if l[0] == "end":
            break
        if l[0] == "insert":
            heapq.heappush(tl,int(l[1]) * -1)
        if l[0] == "extract":
            a = heapq.heappop(tl) * -1 
            print (a)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
Q = []
while True:
    order = input().strip().split()
    if order[0] == 'end':
        break
    elif order[0] == 'insert':
        num = -1 * int(order[1])
        heapq.heappush(Q,num)
    else:
        M = -1 * heapq.heappop(Q)
        print(M)

Solution (Python):
import sys
nodes = ['OFFSET'] + [-1] * 4000000
_num_nodes = 0
outputs = [None] * 2000000
_num_outputs = 0

def max_heapify(idx):
    left_idx = idx * 2
    right_idx = left_idx + 1

    max_idx = idx

    if nodes[left_idx] > nodes[max_idx]:
        max_idx = left_idx
    if nodes[right_idx] > nodes[max_idx]:
        max_idx = right_idx

    if max_idx != idx:
        tmp = nodes[idx]
        nodes[idx] = nodes[max_idx]
        nodes[max_idx] = tmp
        max_heapify(max_idx)
    return


def insert(node_no):
    global _num_nodes
    nodes[_num_nodes+1] = node_no
    _num_nodes += 1
    idx = _num_nodes
    while idx > 1:
        parent_idx = idx // 2
        if nodes[idx] > nodes[parent_idx]:
            tmp = nodes[parent_idx]
            nodes[parent_idx] = nodes[idx]
            nodes[idx] = tmp
        else:
            break
        idx = parent_idx
    return


def extract():
    global _num_outputs
    outputs[_num_outputs] = nodes[1]
    _num_outputs += 1
    global _num_nodes
    nodes[1] = nodes[_num_nodes]
    nodes[_num_nodes] = -1
    _num_nodes -= 1
    max_heapify(1)
    return


def main():
    commands = sys.stdin.readlines()
    for command in commands:
        if command[0] == 'i':
            insert(int(command[7:]))
        elif command[1] == 'x':
            extract()
        elif command[1] == 'n':
            break

    for i in range(_num_outputs):
        print(outputs[i])
    return


main()

Solution (Python):
import heapq

a=[]
heapq.heapify(a)
while(1):
    ope=input().split()
    if(ope[0]=="end"):
        break

    elif(ope[0]=="insert"):
        heapq.heappush(a,-1*int(ope[1]))
       

    elif(ope[0]=="extract"):
        print(f"{-1*heapq.heappop(a)}")

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):
import heapq

A = []

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

Solution (Python):
import heapq

a = []
while True:
  inp = input().split()
  if inp[0] == "insert":
    heapq.heappush(a, -int(inp[1]))
  elif inp[0] == "extract":
    print(-heapq.heappop(a))
  else:
    break

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


def main():
    Q = []

    for line in stdin.readlines():
        cmd = line.split()
        if cmd[0] == "insert":
            heappush(Q, -int(cmd[1]))
        elif cmd[0] == "extract":
            print(-heappop(Q))
        else:
            break


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

tmp_heap = []
while True:
    input_str = input()
    if input_str[2] == 'd':
        break

    if input_str[0] == 'i':
        heappush(tmp_heap,-int(input_str[7:]))
    else:
        print("%d"%(-heappop(tmp_heap)))

Solution (Python):
import heapq
from sys import stdin

def read_and_print_pqueue():
    A = []
    while True:
        cmd = stdin.readline().strip().split()
        if cmd[0][0] == 'i':
            heapq.heappush(A, -int(cmd[1]))
        elif cmd[0][0:2] == 'ex':
            print(-heapq.heappop(A))
        elif cmd[0][0:2] == 'en':
            break

read_and_print_pqueue()

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

queue = []
while True:
    order, *key = sys.stdin.readline().split()
    if order == "insert":
        heappush(queue, -int(key[0]))
    elif order == "extract":
        print(-heappop(queue))
    else:
        break

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

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

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