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: Runtime Error

Solution code:
from sys import stdin, stdout, 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()

Submission status: Runtime Error

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)
    now = len(S) - 1
    while True:
        p = parent(now)
        if p < 0:
            break
        elif S[now] > S[p]:
            S[now], S[p] = S[p], S[now]
        else:
            now = p

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

    now = 0
    while True:
        l, r = left(now), right(now)
        if l < len(S):
            if r >= len(S) or S[now] < S[r] and S[l] < S[r]:
                S[now], S[r] = S[r], S[now]
                now = left
            elif S[now] < S[l] and S[r] < S[l]:
                S[now], S[r] = S[r], S[now]
                now = r
        else:
            break

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: Runtime Error

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: Runtime Error

Solution code:
import sys

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = (i + 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: Runtime Error

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)

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

main()

Submission status: Runtime Error

Solution code:
#coding:utf-8
#1_9_C
s = set()
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "insert":
        l.add(int(cmd[1]))
    else:
        print(max(s))
        l.remove(max(s))

Submission status: Runtime Error

Solution code:
# -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

class PriorityQueue:
    def __init__(self, size):
        self.queue = []

    def insert(self, key):
        self.queue.append(key)
        self.heapIncreaseKey()
        debug(self.queue)

    def heapIncreaseKey(self):
        h = len(self.queue) - 1
        parent = get_parent(h)
        while self.queue[parent] < self.queue[h]:
            self.queue[parent], self.queue[h] = self.queue[h], self.queue[parent]

    def extract(self):
        root = self.queue.pop(0)
        if len(self.queue) > 0:
            self.queue = [self.queue.pop()] + self.queue
            maxHeapify(self.queue)
        debug(self.queue)
        return root

def maxHeapify(A):
    for i in range(int(len(A) / 2), 0, -1):
        maxHeapify2(A, i)

def maxHeapify2(A, i):
    l = 2 * i - 1
    r = 2 * i
    largest = i - 1

    if l < len(A):
        largest = largest if A[largest] > A[l] else l

    if r < len(A):
        largest = largest if A[largest] > A[r] else r

    if largest != i - 1:
        A[largest], A[i - 1] = A[i - 1], A[largest]
        maxHeapify2(A, largest + 1)


def get_parent(size):
    size += 1
    return int(size/2) - 1

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

    while True:
        command = input().split()
        if len(command) == 2:
            queue.insert(int(command[1]))

        if command[0] == "extract":
            print(queue.extract())

        if command[0] == "end":
            sys.exit()

Submission status: Runtime Error

Solution code:
# -*- coding: utf_8 -*-
import sys

level = False
def debug(v):
    if level:
        print(v)

class PriorityQueue:
    def __init__(self, size):
        self.queue = [-1] * size
        self.tail = 0

    def insert(self, key):
        self.queue[tail] = key
        self.tail += 1
        self.heapIncreaseKey()
        debug(self.queue)

    def heapIncreaseKey(self):
        h = self.tail - 1
        parent = get_parent(h)
        while parent >= 0 and self.queue[parent] < self.queue[h]:
            self.queue[parent], self.queue[h] = self.queue[h], self.queue[parent]
            h = parent
            parent = get_parent(h)

    def extract(self):
        root = self.queue[0]
        if len(self.queue) > 0:
            self.queue[0], self.queue[self.tail - 1] = self.queue[tail - 1], -1
            self.tail -=1
            maxHeapify(self.queue)
        debug(self.queue)
        return root

def maxHeapify(A):
    for i in range(int(len(A) / 2), 0, -1):
        maxHeapify2(A, i)

def maxHeapify2(A, i):
    l = 2 * i - 1
    r = 2 * i
    largest = i - 1

    if l < len(A):
        largest = largest if A[largest] > A[l] else l

    if r < len(A):
        largest = largest if A[largest] > A[r] else r

    if largest != i - 1:
        A[largest], A[i - 1] = A[i - 1], A[largest]
        maxHeapify2(A, largest + 1)


def get_parent(size):
    size += 1
    return int(size/2) - 1

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

    while True:
        command = input().split()
        if len(command) == 2:
            queue.insert(int(command[1]))

        if command[0] == "extract":
            print(queue.extract())

        if command[0] == "end":
            sys.exit()

Submission status: Runtime Error

Solution code:
# -*- coding: utf_8 -*-
import sys

level = False
def debug(v):
    if level:
        print(v)

class PriorityQueue:
    def __init__(self, size):
        self.queue = [-1] * size
        self.tail = 0

    def insert(self, key):
        self.queue[self.tail] = key
        self.tail += 1
        self.heapIncreaseKey()
        debug(self.queue)

    def heapIncreaseKey(self):
        h = self.tail - 1
        parent = get_parent(h)
        while parent >= 0 and self.queue[parent] < self.queue[h]:
            self.queue[parent], self.queue[h] = self.queue[h], self.queue[parent]
            h = parent
            parent = get_parent(h)

    def extract(self):
        root = self.queue[0]
        if len(self.queue) > 0:
            self.queue[0], self.queue[self.tail - 1] = self.queue[self.tail - 1], -1
        self.tail -=1
        maxHeapify(self.queue, self.tail)
        debug(self.queue)
        return root

def maxHeapify(A, size):
    for i in range(int(size / 2), 0, -1):
        maxHeapify2(A, i, size)

def maxHeapify2(A, i, size):
    l = 2 * i - 1
    r = 2 * i
    largest = i - 1

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

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

    if largest != i - 1:
        A[largest], A[i - 1] = A[i - 1], A[largest]
        maxHeapify2(A, largest + 1)


def get_parent(size):
    size += 1
    return int(size/2) - 1

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

    while True:
        command = input().split()
        if len(command) == 2:
            queue.insert(int(command[1]))

        if command[0] == "extract":
            print(queue.extract())

        if command[0] == "end":
            sys.exit()

Submission status: Runtime Error

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

import sys


def max_heapify(index):
    left, right, largest = 2 * index, 2 * index + 1, None

    if left <= heap_length and heap_array[left] > heap_array[index]:
        largest = left
    else:
        largest = index

    if right <= heap_length and heap_array[right] > heap_array[largest]:
        largest = right

    if largest != index:
        heap_array[index], heap_array[largest] = heap_array[largest], heap_array[index]
        max_heapify(largest)

    return None


def extract():
    global heap_length
    if heap_length < 1:
        raise SystemExit('Heap underflow!')
    heap_max = heap_array[1]
    heap_array[1] = heap_array[heap_length]
    heap_length -= 1
    # print('max', heap_max, heap_length, heap_array)
    print(heap_max)
    max_heapify(1)
    return heap_max


def insert(data):
    global heap_length
    heap_length += 1
    heap_array.append(-1)
    # print(heap_length, heap_array)
    # assert len(heap_array) == heap_length + 1
    insert_data(heap_length, data)


def insert_data(index, data):
    if data < heap_array[index]:
        raise SystemExit('Not a max-heap!')
    heap_array[index] = data
    while index > 1:
        parent = index // 2
        if heap_array[parent] >= heap_array[index]:
            break
        heap_array[index], heap_array[parent] = heap_array[parent], heap_array[index]
        index //= 2
    return None


def action(_command, _content):
    if _command.startswith('in'):
        insert(int(_content))
    elif _command.startswith('ex'):
        extract()
    else:
        pass

    return None


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

    allowed_commands = ('insert', 'extract', 'end')
    heap_array, heap_length = [None], 0
    for each in command_list:
        command, content = each[0], each[-1]
        if command not in allowed_commands:
            raise SystemExit('Illegal command!')

        action(command, content)

Submission status: Runtime Error

Solution code:
import sys
from numpy import inf

def insert(heap, key):
    heap.append(-inf)
    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 = []
out = ''
for line in sys.stdin:
    while line[0:2] != 'en':
        if line[0] == 'i':
            insert(heap, int(line.split()[1]))
        if line[0:2] == 'ex':
            print(str(heapExtractMax(heap)))

Submission status: Runtime Error

Solution code:
import sys
from numpy import inf

def insert(heap, key):
    heap.append(-inf)
    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 = []
out = ''
while True:
    line = 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: Runtime Error

Solution code:
import sys
from numpy import inf

def insert(heap, key):
    heap.append(-inf)
    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: Runtime Error

Solution code:
import bisect
from collections import deque
maxv = 0
l = deque()
while True:
    order = input()
    if order == "end":
        break
    tmp = order.split()
    if len(tmp) > 1:
        v = int(tmp[1])
        bisect.insort(l, v)
        maxv = l[-1]
    else:
        print(maxv)
        l.pop()
        maxv = l[-1] if len(l) else 0

Submission status: Runtime Error

Solution code:
import sys

heap = [0]
NIL = -1


def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


def insert(key):
    H = len(heap) - 1
    heap.append(NIL)
    heapIncreaseKey(H, key)


def heapIncreaseKey(i, key):
    if key < heap[i]:
        return False
    heap[i] = key
    while i > 1 and heap[parent(i)] < heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)


def heapExtractMax():
    H = len(heap) - 1
    if H < 1:
        return False
    max = heap[1]
    heap[1] = heap[H]
    heap.pop(H)
    maxHeapify(1)

    return max


def maxHeapify(i):
    H = len(heap) - 1
    l = left(i)
    r = right(i)
    if l <= H and heap[l] > heap[i]:
        largest = l
    else:
        largest = i

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

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

for com in sys.stdin.readlines():
    if com[0] == "i":
        heap.insert(int(com[7:]))
    elif com[1] == "x":
        print(heap.heapExtractMax())

Submission status: Runtime Error

Solution code:
def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


def insert(key):
    heap.append(NIL)
    H = len(heap) - 1
    heapIncreaseKey(H, key)


def heapIncreaseKey(i, key):
    if key < heap[i]:
        return False
    heap[i] = key
    while i > 1 and heap[parent(i)] < heap[i]:
        heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
        i = parent(i)


def heapExtractMax():
    H = len(heap) - 1
    if H < 1:
        return False
    max = heap[1]
    heap[1] = heap[H]
    heap.pop(H)
    maxHeapify(1)

    return max


def maxHeapify(i):
    H = len(heap) - 1
    l = left(i)
    r = right(i)
    if l <= H and heap[l] > heap[i]:
        largest = l
    else:
        largest = i

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

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

while True:
    cmd = list(input().split())
    if cmd[0] == 'insert':
        insert(int(cmd[1]))
    elif cmd[0] == 'extract':
        print(heapExtractMax())
    else:
        break

Submission status: Runtime Error

Solution code:
# ?§£???2
from math import inf
from math import floor

def maxheapfi(i):
    global H
    global A
    l = 2 * (i  + 1) - 1 
    r = 2 * (i  + 1) 

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

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

    if largest != i:
        tmp = A[i-1]
        A[i-1] = A[largest]
        A[largest] = tmp
        maxheapfi(largest,A,H)
    
def extract():
    global H
    global A
    if H < 0 : return -inf
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    maxheapfi(0)
    return maxv

def increasekey(i, key):
    global H
    global A
    if key < A[i - 1]:
        return
    A[i - 1] = key
    while( i > 0 and A[floor(i/2)-1] < A[i-1]):
        tmp = A[i-1]
        A[i - 1] = A[floor(i/2) - 1] 
        A[floor(i/2) - 1]  = tmp
        i = floor(i/2) - 1
    
        
def insert(key):
    global H
    global A
    H += 1
    if len(A) <= H:
        A.append(-inf)
    else:
        A[H-1] = -inf
    increasekey(H,key)

def main():
    global H
    global A
    H = 0
    A = []
    opr = [x.strip().split(' ') for x in open('./input/B1.txt').readlines()]
    H = int(input().strip())
    For i in range(H):
        opr.append(input().strip().split(??? ???))
    for i in opr:
        if i[0] == 'insert':
            insert(int(i[1]))
        if i[0] == 'extract':
            print(extract())
            
main()

Submission status: Runtime Error

Solution code:
# ?§£???2
from math import inf
from math import floor

def maxheapfi(i):
    global H
    global A
    l = 2 * (i  + 1) - 1 
    r = 2 * (i  + 1) 

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

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

    if largest != i:
        tmp = A[i-1]
        A[i-1] = A[largest]
        A[largest] = tmp
        maxheapfi(largest,A,H)
    
def extract():
    global H
    global A
    if H < 0 : return -inf
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    maxheapfi(0)
    return maxv

def increasekey(i, key):
    global H
    global A
    if key < A[i - 1]:
        return
    A[i - 1] = key
    while( i > 0 and A[floor(i/2)-1] < A[i-1]):
        tmp = A[i-1]
        A[i - 1] = A[floor(i/2) - 1] 
        A[floor(i/2) - 1]  = tmp
        i = floor(i/2) - 1
    
        
def insert(key):
    global H
    global A
    H += 1
    if len(A) <= H:
        A.append(-inf)
    else:
        A[H-1] = -inf
    increasekey(H,key)

def main():
    global H
    global A
    H = 0
    A = []
    #opr = [x.strip().split(' ') for x in open('./input/B1.txt').readlines()]
    H = int(input().strip())
    for i in range(H):
        opr.append(input().strip().split(' '))
    for i in opr:
        if i[0] == 'insert':
            insert(int(i[1]))
        if i[0] == 'extract':
            print(extract())
            
main()

Submission status: Runtime Error

Solution code:
# ?§£???2
from math import inf
from math import floor

def maxheapfi(i):
    global H
    global A
    l = 2 * (i) + 1  
    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
    #print('largest',largest)
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        maxheapfi(largest)
    
def extract():
    global H
    global A
    if H < 0 : return -inf
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    maxheapfi(0)
    #print(32,A)
    return maxv

def increasekey(i, key):
    global H
    global A
    if key < A[i]:
        return
    A[i] = key
    while( i > 0 and A[floor(i/2)] < A[i]):
        tmp = A[i]
        A[i] = A[floor(i/2) ] 
        A[floor(i/2)]  = tmp
        i = floor(i/2)
        #print(46,i,key,A)
    
        
def insert(key):
    global H
    global A
    H += 1
    if len(A) < H:
        A.append(-inf)
    else:
        A[H-1] = -inf
    #print('increasekey',H-1,key)
    increasekey(H-1,key)

def main():
    global H
    global A
    H = 0
    A = []
    opr = None
    count = 0
    while(True):
        opr = input().strip().split(' ')
        if opr[0] == 'insert':
            insert(int(opr[1]))
            #print(A)
        if opr[0] == 'extract':
            print(extract())
            #print(A)
        if opr[0] == 'end':
            break
        
main()

Submission status: Runtime Error

Solution code:
from math import inf
from math import floor

def maxheapfi(i):
    global H
    global A
    l = 2 * (i) + 1  
    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
    #print('largest',largest)
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        maxheapfi(largest)
    
def extract():
    global H
    global A
    if H < 0 : return -inf
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    maxheapfi(0)
    #print(32,A)
    return maxv

def increasekey(i, key):
    global H
    global A
    if key < A[i]:
        return
    A[i] = key
    while( i > 0 and A[floor(i/2)] < A[i]):
        tmp = A[i]
        A[i] = A[floor(i/2) ] 
        A[floor(i/2)]  = tmp
        i = floor(i/2)
        #print(46,i,key,A)
    
        
def insert(key):
    global H
    global A
    H += 1
    if len(A) < H:
        A.append(-inf)
    else:
        A[H-1] = -inf
    #print('increasekey',H-1,key)
    increasekey(H-1,key)

def main():
    global H
    global A
    H = 0
    A = []
    opr = None
    count = 0
    while(True):
        opr = input().strip().split(' ')
        if opr[0] == 'insert':
            insert(int(opr[1]))
            #print(A)
        if opr[0] == 'extract':
            print(extract())
            #print(A)
        if opr[0] == 'end':
            break
        
main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    q =deque()
    H = 0
    for i in range(int(2e+06)):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q.append(int(cmd[1]))
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q.popleft()
            H -= 1
            buildMaxHeap(q,H)
        else:
            break

def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            v = A[p-1]
            A[p-1] = A[i-1]
            A[i-1] = v
            increase(A,p)
            
def maxHeapify(A,i,H):
    l = 2*i
    r = 2*i+1
    if l <= H and A[l-1] > A[i-1]:
        largest = l
    else:
        largest = i
    if r <= H and A[r-1] > A[largest-1]:
        largest = r

    if largest != i:
        v = A[i-1]
        A[i-1] = A[largest-1]
        A[largest-1] = v
        maxHeapify(A,largest,H)

def buildMaxHeap(A,H):
    for j in range(H/2):
        i = H/2-j
        maxHeapify(A,i)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    q = []
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q.append()=int(cmd[1])
        elif cmd[0] == "extract":
            ret = max(q)
            print ret
            q.remove(ret)
        else:
            break
 
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a = []
while True:
    inp = input()
    if inp[0] == "i":
        a.append(int(inp[7:]))
    elif inp[0] == "e":
        a.sort()
        print(a.pop())
    else:
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def parent(i):
    return i // 2


def left(i):
    return 2 * i


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

class MaxHeap(list):
    def __init__(self, H=0):
        list.__init__(self)
        self.H = H
        self[:] = [None] * (H+1)

    def insert(self, key):
        self.H += 1
        self.append(-float("inf"))
        self.heapIncreaseKey(self.H, key)

    def heapIncreaseKey(self, i, key):
        if key < self[i]:
            raise "error"
        self[i] = key
        while i > 1 and self[parent(i)] < self[i]:
            self[i], self[parent(i)] = self[parent(i)], self[i]

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = A[self.H]
        self.H -= 1
        self.maxHeapify(1)

        return maximum

    def maxHeapify(self, i):
        l = left(i)
        r = right(i)
        if l <= self.H and self[l] > self[i]:
            largest = l
        else:
            largest = i
        if r <= self.H and self[r] > self[largest]:
            largest = r

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

        


if __name__ == '__main__':

    A = MaxHeap()
    c = [None, None]
    while c[0] != "end":
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            pass

Submission status: Runtime Error

Solution code:
def maxHeapify(A, i, n):
    l = i * 2 + 1
    r = i * 2 + 2
    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(S, k):
    S.append(k)
    n = len(S)
    i = n - 1
    while i > 0 and S[i] > S[(i - 1) // 2]:
        S[i], S[(i - 1) // 2] = S[(i - 1) // 2], S[i]
        i = (i - 1) // 2
def extractMax(S):
    if len(S) == 1:
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    maxHeapify(S, 0, len(S))
    return ans
A = []
while True:
    s = input()
    if s == "end":
        break
    elif s == "extract":
        print(extractMax(A))
    else:
       insert(A, int(s[7:]))

Submission status: Runtime Error

Solution code:
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]
for a in iter(input,'end'):
 if a[0]=='i':
  H+=1;A+=[int(a[7:])];k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k/=2
 else:
  print(A[1])
  if H-1:A[1]=A.pop()
  H-=1;h(1)

Submission status: Runtime Error

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+=f'{-heappop(H)}\n')
print(O[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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