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 sys import stdin
from heapq import heappop, heappush
readline = stdin.readline


heap = []
while True:
    line = readline()
    if line[1] == 'x':print(-heappop(heap))
    elif line[0] == 'i':heappush(heap, -int(line.split()[1]))
    else:break

Submission status: Accepted

Solution code:
import sys
import heapq

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
import heapq

# main
q = []
S = sys.stdin.readlines()
for line in S:
    if line[0].startswith('i'):
        heapq.heappush(q, -int(line.split()[1]))
    elif line[1] == 'x':
        print(-heapq.heappop(q))
    else:
        exit()

Submission status: Accepted

Solution code:
from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

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

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

heap = []

while True:
    l = input()
    if l.startswith('i'):
        heappush(heap, -int(l.split()[1]))
    elif l[1] == 'x':
        print(-heappop(heap))
    else:
        break

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
from collections import deque
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = deque([]) 

def maxHeapify(i):
    global a, h
    l = 2 * i
    r = 2 * i + 1
    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(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print("\n".join([str(s) for s in list(ret)]))
        # print()

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
from collections import deque
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = deque([])

def maxHeapify(i):
    global a, h
    l = 2 * i
    r = 2 * i + 1
    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(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

i = 0
for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract())
    else:
        sys.stdout.writelines("\n".join([str(s) for s in ret]))
        print()

Submission status: Accepted

Solution code:
import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))

Submission status: Accepted

Solution code:
import heapq


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

Submission status: Accepted

Solution code:
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey
    setHeapDown_max(heap, pos)

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        print(heapPop_max(S))
    else:
        pass

Submission status: Accepted

Solution code:
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        childkey = heap[childpos]
        if targetkey > childkey:
            break
        heap[pos] = childkey
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        print(heapPop_max(S))
    else:
        pass

Submission status: Accepted

Solution code:
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        childkey = heap[childpos]
        if targetkey > childkey:
            break
        heap[pos] = childkey
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

ans = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        ans.append(heapPop_max(S))
    else:
        pass

print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey
    setHeapDown_max(heap, pos)

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

ans = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        ans.append(heapPop_max(S))
    else:
        pass

print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    #print S

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()
    size = len(S)

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if l < size and S[idx] < S[l] and (r < size and S[r] <= S[l] or r >= size):
            S[idx], S[l] = S[l], S[idx]
            idx = l
        elif r < size and S[idx] < S[r]:
            S[idx], S[r] = S[r], S[idx]
            idx = r
        else:
            break
    #print S

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

Submission status: Accepted

Solution code:
import sys

def parent(i):
    return (i + 1) / 2 - 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

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

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

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

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

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()
    maxHeapify(S, 0, len(S))

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

Submission status: Accepted

Solution code:
import sys

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = (idx + 1) / 2 - 1
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

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

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

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

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

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()
    maxHeapify(S, 0, len(S))

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

Submission status: Accepted

Solution code:
import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

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

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()

Submission status: Accepted

Solution code:
#coding:utf-8
#1_9_C
import heapq

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

Submission status: Accepted

Solution code:
from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')

Submission status: Accepted

Solution code:
import heapq
queue = []
targ = input()
while targ != "end":
    if targ[0] == "i":
        heapq.heappush(queue,-int(targ.split(' ')[1]))
    else:
        print(-heapq.heappop(queue))
    targ = input()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


import heapq
import sys


def main():
    pq = []
    for line in sys.stdin:
        args = line.split()
        if args[0] == "insert":
            heapq.heappush(pq, -int(args[1]))
        elif args[0] == "extract":
            print(-heapq.heappop(pq))
        else:
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import heapq

A = []
inp = input()
while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(-heapq.heappop(A))
    elif inp[0] == 'i':
        heapq.heappush(A, -int(inp[7:]))
    inp = input()

Submission status: Accepted

Solution code:
import sys
import heapq

heap = []

while True:
    input_line = input()
    input_line = input_line.strip().split()

    # print(input_line[0] == "insert")
    if str(input_line[0]) == 'insert':
        heapq.heappush(heap, -int(input_line[1]))
    elif str(input_line[0]) == "extract":
        print(-heapq.heappop(heap))
    else:
        break

Submission status: Accepted

Solution code:
import heapq
pq = []
while True:
    c = input().split()
    if c[0] == 'end':
        break
    if c[0] == 'extract':
        print(-heapq.heappop(pq))
    else:
        heapq.heappush(pq, -int(c[1]))

Submission status: Accepted

Solution code:
from heapq import *
import sys
q=[]
while True:
	a=sys.stdin.readline().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
import sys
 
h = []
 
for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import heapq as hp

# import heapq
# import sys
#
# h = []
#
# for com in sys.stdin.readlines():
#     if com[0] == "i":
#         heapq.heappush(h, -int(com[7:]))
#     elif com[1] == "x":
#         print(-heapq.heappop(h))

if __name__ == '__main__':
    _input = sys.stdin.readlines()
    # command_list = list(map(lambda x: x.split(), _input))

    allowed_commands = ('insert', 'extract', 'end')
    heap_array = []
    for each in _input:
        # command, content = each[0], each[-1]
        # if command not in allowed_commands:
        #     raise SystemExit('Illegal command!')
        if each.startswith('in'):
            hp.heappush(heap_array, -1 * int(each[7:]))
        elif each.startswith('ex'):
            print(-1 * hp.heappop(heap_array))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import heapq as hp

if __name__ == '__main__':
    _input = sys.stdin.readlines()

    heap_array = []
    for each in _input:
        if each.startswith('in'):
            hp.heappush(heap_array, -1 * int(each[7:]))
        elif each.startswith('ex'):
            print(-1 * hp.heappop(heap_array))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

if __name__ == '__main__':
    # ??????????????\???
    # ???????????????
    h = []
    while True:
        raw_input = input()
        if raw_input == 'extract':
            pri, item = heappop(h)
            print(item)
        elif raw_input == 'end':
            break
        else:
            cmd, pri = raw_input.split()
            heappush(h, (-1*int(pri), pri))

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ????????????????????£????????\??? '''

import heapq


class PQueue(object):
    """ Priority Queue """

    def __init__(self):
        self.pqueue = []

    def insert(self, x):
        # self.pqueue.append(x)
        heapq.heappush(self.pqueue, -x)

    def extractMax(self):
        # return self.pqueue.pop(self.pqueue.index(max(self.pqueue)))
        return -heapq.heappop(self.pqueue)


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

    while True:
        line = input()
        if line == 'end':
            break

        if line.split()[0] == 'insert':
            pqueue.insert(int(line.split()[1]))
        elif line.split()[0] == 'extract':
            result.append(pqueue.extractMax())

    for i in range(len(result)):
        print(result[i])

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

heap = []

while 1:
    cmd = sys.stdin.readline().split()

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

    if cmd[0] == 'extract':
        print(-heappop(heap))
    else:
        heappush(heap, -int(cmd[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 sys import stdin
from heapq import heappop, heappush
readline = stdin.readline

heap = []
while True:
    line = readline()
    if line[1] == 'x':
        print(-heappop(heap))
    elif line[0] == 'i':
        heappush(heap, -int(line.split()[1]))
    else:
        break


'''
def insert(heap, key):
    heap.append(-1000000)
    heapIncreaseKey(heap, key)

def parent(i):
    return (i - 1) // 2

def heapIncreaseKey(heap, key):
    heap[len(heap) - 1] = key
    i = len(heap) - 1
    while i > 0 and heap[parent(i)] < heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)

def heapExtractMax(heap):
    if len(heap) < 1:
        return None
    else:
        MAX = heap[0]
        heap[0] = heap.pop()
        maxHeapify(heap, 0)

        return MAX

def maxHeapify(heap, i):
    left = (i + 1) * 2 - 1
    right = (i + 1) * 2
    largest = left if left < len(heap) and heap[left] > heap[i] else i
    largest = right if right < len(heap) and heap[right] > heap[largest] else largest
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        maxHeapify(heap, largest)


heap = []
while True:
    line = sys.stdin.readline()
    if line[0] == 'i':
        insert(heap, int(line.split()[1]))
    elif line[0:2] == 'ex':
        print(str(heapExtractMax(heap)))
    else:
        break
'''

Submission status: Accepted

Solution code:
import sys

def max_heapify(A, H, i):
  target = A[i]

  m = i
  l = i * 2
  while l <= H:
    largest = target
    if A[l] > target:
      m = l
      largest = A[m]

    r = l + 1
    if r <= H and A[r] > largest:
      m = r
      largest = A[m]

    if m != i:
      A[i] = largest
      i = m
      l = i * 2
    else:
      break

  A[m] = target

def build_max_heap(A, i):
  if i < 2: return
  last = A[i]
  p = i // 2
  while p > 0 and A[p] < last:
    A[i] = A[p]
    i = p
    p = i // 2
  A[i] = last

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A, len(A) - 1)
  elif line[1] == 'x':
    if len(A) <= 1:
      pass
    elif len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, len(A) -1, 1)
  else:
    exit()

Submission status: Accepted

Solution code:
import heapq
pq = []

def insert(S,k):
    heapq.heappush(pq, - k)

def extractMax(S):
    a = - heapq.heappop(S)
    print(str(a))

L = input()
while L != "end":
    if L =="extract":
        extractMax(pq)
    else:
        L = L.split()
        insert(pq, int(L[1]))
    L = input()

Submission status: Accepted

Solution code:
import heapq
command = input().split()
h = []
while command[0] != "end":
    if command[0] == "insert":
        heapq.heappush(h, -int(command[1]))
    else:
        print(-heapq.heappop(h))
    command = input().split()

Submission status: Accepted

Solution code:
import heapq

H = []

#heappop???pop????????????heap??????????°????????´??????????
#????????§?????????????????´???????¬??????????????????????????????????

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

    if line[0] == 'insert':
        heapq.heappush(H,-int(line[1]))
    elif line[0] == 'extract':
        print(-heapq.heappop(H))
    else:
        break

Submission status: Accepted

Solution code:
import sys

#@profile
def max_heapify(A, i):
    j = i
    largest = i
    H = len(A) -1
    while True:
        l = j * 2
        r = l + 1
        if l <= H and A[l] > A[j]:
            largest = l
        if r <= H and A[r] > A[largest]:
            largest = r
        if largest != j:
            A[j], A[largest] = A[largest], A[j]
            #max_heapify(A, largest)
            j = largest
            
        else:
            break
        

#@profile
def build_max_heap(A):
    i = len(A)-1
    last = A[i]
    parent = i//2
    while  parent > 0 and A[parent] < last:
        A[i] = A[parent]
        i = parent
        parent = i //2
    A[i] = last

#@profile
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
A = [0]

#@profile
def main():
    out = ""
    for l in sys.stdin.readlines():
        if l[0] == "i":
            #insert k
            A.append(int(l[7:]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(out, end = "")
            return
        else:
            if len(A) <= 1:
                pass
            elif len(A) == 2:
                out += str(A.pop()) + "\n"
                #print(A.pop())
            #extract(A)
            else:
                out += str(A[1]) + "\n"
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

if __name__ == "__main__":
    a = []
    heapq.heapify(a)
    for inp in sys.stdin.readlines():
        inp = inp.split()
        if inp[0] == "insert":
            heapq.heappush(a, int(inp[1])*(-1))
        elif inp[0] == "extract":
            print((-1)*heapq.heappop(a))

Submission status: Accepted

Solution code:
import sys
import heapq

if __name__ == "__main__":
    a = []
    for inp in sys.stdin.readlines():
        inp = inp.split()
        if inp[0] == "insert":
            heapq.heappush(a, -int(inp[1]))
        elif inp[0] == "extract":
            print(-heapq.heappop(a))

Submission status: Accepted

Solution code:
import heapq

def main():
    q = []
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            heapq.heappush(q,-int(cmd[1]))
        elif cmd[0] == "extract":
            print -heapq.heappop(q)
        else:
            break

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

q = []

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

A = []
inp = [None]
while inp[0] != "end":
    inp = input().split()
    if inp[0] == "insert":
        heappush(A, -int(inp[1]))
    elif inp[0] == "extract":
        print(-heappop(A))

Submission status: Accepted

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

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:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop

if __name__ == '__main__':

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

Submission status: Accepted

Solution code:
import heapq

heap = []

while True:

    inst = input()
    if inst[0] == "i":
        heapq.heappush(heap, -int(inst[7:]))
    elif inst[1] == "x":
        print(-heapq.heappop(heap))
    else:
        break

Submission status: Accepted

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

Submission status: Accepted

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

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