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

Submission status: Accepted

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

Submission status: Accepted

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

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*

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/9/ALDS1_9_C
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
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#組込み関数頼み
import heapq
H=[]

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

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from copy import deepcopy
import heapq
#import math
#import string
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))
        
# これさー、heapq自体を実装することに意味があるんじゃないの？
# heqpq使ったらあんまり意味がない気がする
# Pythonだと間に合わないのだろうかーーーー

Submission status: Accepted

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



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

Submission status: Accepted

Solution code:
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('想定外の事態')

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C&lang=jp
# Priority Queue
# 2018.12.09 yonezawa

#from collections import deque
import sys
input = sys.stdin.readline
import heapq
#import cProfile

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()
   #pr = cProfile.Profile()
   #pr.runcall(main)
   #pr.print_stats()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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:
# Heaps - Priority Queue
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()

Submission status: Runtime Error

Solution code:
#coding: utf-8
A = []
inf = 100000000000

def maxHeapify(A, i):
    l = 2 * i
    r = 2 * i  + 1
    H = len(A)

    if l <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r <= H and A[r] > A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]                                                                                                                                    
        maxHeapify(A, largest)

        
def Insert(key):
    A.append(key)
    i = len(A)
    while i > 1 and A[i // 2 - 1] < A[i-1] :
        A[i-1], A[i // 2 - 1] = A[i // 2 - 1], A[i - 1]
        i = i// 2

def heapExtractMax(A):
    if len(A) == 0:
        return
    maxv = A[0]
    A[0] = A[-1]
    maxHeapify(A, 0)

    return maxv

while True:
    data = list(input().split())
    if data[0] == "end":
        break
    elif data[0] == "insert":
        Insert(int(data[1]))
    else:
        maxv = heapExtractMax(A)
        print(maxv)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>

#define SIZE 2000000

int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp;
  char com[20];
  do {
    fgets(com, 20, stdin);
    if (com[0] == 'i') { // insert nn
      A[++H] = atoi(com+7);    
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
         largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>

#define SIZE 2000000

int myatoi(const char* p)
{
  int n;
  while (*p!='\n') {
    n = n*10+*p-'0';
    p++;
  }
  return n;
}

void putnum(int n)
{
  int i;
  char buf[20];
  buf[19]='\0';
  for (i=18; n>0; n/=10) buf[i--]=(n%10)+'0';
  puts(buf+i+1);
}javascript:void(0)

int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp;
  char com[21];
  do {
    fgets(com, 20, stdin);
    if (com[0] == 'i') {
      A[++H] = myatoi(com+7);
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }
    } else if (com[1]=='x') { // extract
      putnum(A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
        largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>

#define SIZE 2000000

int myatoi(const char* p)
{
  int n;
  while (*p!='\n') {
    n = n*10+*p-'0';
    p++;
  }
  return n;
}

void putnum(int n)
{
  int i;
  char buf[20];
  buf[19]='\0';
  for (i=18; n>0; n/=10) buf[i--]=(n%10)+'0';
  puts(buf+i+1);
}

int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp;
  char com[21];
  do {
    fgets(com, 20, stdin);
    if (com[0] == 'i') {
      A[++H] = myatoi(com+7);
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }
    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]); //putnum(A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
        largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>

#define SIZE 2000000

int myatoi(const char* p)
{
  int n;
  while (*p!='\n') {
    n = n*10+*p-'0';
    p++;
  }
  return n;
}

int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp;
  char com[21];
  do {
    fgets(com, 20, stdin);
    if (com[0] == 'i') {
      A[++H] = myatoi(com+7);
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
        largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>

#define SIZE 2000000

int myatoi(const char* p)
{
  int n;
  while (*p!='\n') {
    n = n*10+*p-'0';
    p++;
  }
  return n;
}

int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp;
  char com[21];
  do {
    fgets(com, 20, stdin);
    if (com[0] == 'i') {
      A[++H] = atoi(com+7);
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
        largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>

#define SIZE 2000000

int myatoi(const char* p)
{
  int n;
  while (*p!='\n' && *p!='\r') {
    n = n*10+*p-'0';
    p++;
  }
  return n;
}

int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp;
  char com[21];
  do {
    fgets(com, 20, stdin);
    if (com[0] == 'i') {
      A[++H] = myatoi(com+7);
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
        largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

Submission status: Runtime Error

Solution code:
def get_parent(A, i):
    if i == 1:
        return None
    else:
        return i // 2

def get_left(A, i):
    if len(A) > 2 * i:
        return 2 * i
    else:
        return None

def get_right(A, i):
    if len(A) > 2 * i + 1:
        return 2 * i + 1
    else:
        return None

A = [-1] * 10
H = 0

def insert(A, key):
    global H
    H += 1
    A[H] = key
    i = H
    while i > 1:
        # print(i)
        parent = get_parent(A, i)
        if parent is None:
            break
        if A[parent] < A[i]:
            # print('swap', i, parent, A[i], A[parent])
            tmp = A[i]
            A[i] = A[parent]
            A[parent] = tmp
            i = parent
        else:
            break

def max_heapfy(A, i):
    left = get_left(A, i)
    right = get_right(A, i)
    largest = i
    if left and A[left] > A[i]:
        largest = left
    if right and A[right] > A[largest]:
        largest = right
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        max_heapfy(A, largest)

def extract_max(A):
    global H
    max_value = A[1]
    A[1] = A[H]
    A[H] = -1
    H -= 1
    max_heapfy(A, 1)
    return max_value

# Heap heap ヒープの実装はここを参考にした
# http://ikapblg.blog.fc2.com/blog-entry-57.html

def print_heap(A):
    for index, elem in enumerate(A):
        if index == 0:
            continue
        if elem == -1:
            break
        print(elem)

while True:
    line = input().split()
    if line[0] == 'insert':
        insert(A, int(line[1]))
        # print(A)
    elif line[0] == 'extract':
        max_value = extract_max(A)
        print(max_value)

    else:
        # print('end:')
        # print_heap(A)
        break

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;


void insert(vector<int> &p_q,int last,int val){
    p_q.push_back(val);
    last++;
    int last_p = (last-1)/2;
    while(last >= 0 && p_q[last] > p_q[last_p]){
        swap(p_q[last],p_q[last_p]);
        last = last_p;
        last_p = ((last-1)/2);
    }
}

void make_heap(vector<int> &p_q,int size,int idx){
    int left  = 2*idx+1;
    int right = left+1;

    int max_i = idx;
    if(left < size && p_q[left] > p_q[idx])
        max_i = left;
    if(right < size && p_q[right] > p_q[max_i])
        max_i = right;
    
    if(max_i != idx){
        swap(p_q[idx],p_q[max_i]);
        make_heap(p_q,size,max_i);
    }
}

void extract(vector<int> &p_q){
    int size = p_q.size();
    if(size < 1) return;
    int ret = p_q[0];
    p_q[0] = p_q[size-1];
    p_q.pop_back();
    make_heap(p_q,size,0);

    cout << ret << endl;
}

void print_queue(vector<int> &p_q){
    for(int i=0;i<p_q.size();i++)
        cout << p_q[i] << " ";
    cout << endl;
}

int main(){
    string order;
    int val;
    vector<int> p_queue;

    while(1){
        cin >> order;
        if(order == "insert"){
            cin >> val;
            insert(p_queue,p_queue.size()-1,val);
        }
        else if(order == "extract"){
           extract(p_queue);
        }
        else if(order == "end")
            break;
        else print_queue(p_queue);

    }

}

Submission status: Runtime Error

Solution code:
import asyncio

PQ = asyncio.PriorityQueue()

while True:
    line = input().split()
    if line[0] == 'insert':
        PQ.put_nowait( line[1] )
    elif line[0] == 'extract':
        print(PQ.get_nowait())
    else:
        break

Submission status: Runtime Error

Solution code:
def insert(array, new_value)
  array << new_value
  current = array.size-1
  parent = current / 2
  while (parent > 0) do
    if (array[parent] < array[current]) then
      array[parent], array[current] = array[current], array[parent]
      current = parent
      parent = current / 2
    else
      break
    end
  end
end

def extract(array)
  return nil if array.size == 1
  array[1], array[-1] = array[-1], array[1]
  max = array.pop

  current = 1
  loop do
    bigger_child = get_bigger_child(array, current)
    break if bigger_child == nil
    break if array[current] >= bigger_child[0]
    array[current], array[bigger_child[1]] = array[bigger_child[1]], array[current]
    current = bigger_child[1]
  end

  return max
end

def get_bigger_child(array, i)
  return nil if array.size <= i*2
  return [array[i*2], i*2] if array.size == (i*2 + 1)

  left = [array[i*2], i*2]
  right = [array[i*2+1], i*2+1]
  return [left, right].max_by{|x| x[0]}
end


# main
array = [nil]
while line = gets do
  inputs = line.chomp.split
  if (inputs[0] == 'insert') then
    insert(array, inputs[1].to_i)
  elsif (inputs[0] == 'extract') then
    puts extract(array)
  else
    break
  end
end

Submission status: Runtime Error

Solution code:
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():
    ret = []
    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':
            ret.append(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            sys.stdout.writelines("\n".join([str(s) for s in ret]))
            print()
            exit(0)
  
  
main()