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: Time Limit Exceeded

Solution code:
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)

def insert_heap(i, node_list):
    node_list.append(i)
    k = len(node_list) - 1
    while(node_list[k] > node_list[(k-1)//2] and k > 0):
        node_list[k], node_list[(k-1)//2] = node_list[(k-1)//2], node_list[k]
        k = (k-1)//2


def extract_heap(node_list):
    print(node_list[0])
    pop = node_list.pop()
    n = len(node_list)
    if n != 0:
        node_list[0] = pop
        maxHeapify(0, node_list)

import sys
input_list = sys.stdin.readlines()
node_list = []
for line in input_list:
    line = line.split()
    if line[0] == 'end':
        break
    elif line[0] == 'extract':
        extract_heap(node_list)
    else:
        insert_heap(int(line[1]), node_list)

Submission status: Time Limit Exceeded

Solution code:
queue, ans = [], []

while True:
    s = input()
    if s == 'end':
        break
    elif s == 'extract':
        queue.sort()
        ans.append(queue.pop())
    else:
        t = int(s.strip('insert '))
        queue.append(t)

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


heap = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        print(heap[0])
        heap = heap[1:]
        build_max_heap(heap)
    elif s[0] == "insert":
        heap.append(int(s[1]))
        build_max_heap(heap)

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


heap = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        build_max_heap(heap)
        print(heap[0])
        heap = heap[1:]
        build_max_heap(heap)
    elif s[0] == "insert":
        heap.append(int(s[1]))

Submission status: Time Limit Exceeded

Solution code:
import heapq


def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


heap = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        # build_max_heap(heap)
        # print(heap[0])
        # heap = heap[1:]
        # build_max_heap(heap)
        heapq.heapify(heap)
        print(heapq.heappop(heap)[1])
    elif s[0] == "insert":
        heapq.heappush(heap, (-int(s[1]), int(s[1])))

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


heap = []
ans = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        build_max_heap(heap)
        ans.append(heap[0])
        heap = heap[1:]
        build_max_heap(heap)
    elif s[0] == "insert":
        heap.append(int(s[1]))

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[len(a) - 1]
    build_max_heap(a[:-1])
    return max


heap = []
ans = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        ans.append(heap[0])
        heap = heap[1:]
        build_max_heap(heap)
    elif s[0] == "insert":
        heap.append(int(s[1]))
        build_max_heap(heap)

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[-1]
    a.pop()
    build_max_heap(a)
    return max


heap = []
ans = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        ans.append(extract_max(heap))
    elif s[0] == "insert":
        heap.append(int(s[1]))
        build_max_heap(heap)

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

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

heap = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        print(extractMax(heap))
    elif s[0] == "insert":
        insert(heap, int(s[1]))

Submission status: Time Limit Exceeded

Solution code:
import sys


def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[-1]
    a.pop()
    build_max_heap(a)
    return max

def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    end = False
    heap = []
    for cmd in cmds:
        if cmd == "end":
            end = True
            break
        elif cmd == "extract":
            print(extract_max(heap))
        elif cmd[0] == "i":
            heap.append(int(cmd[7:]))
            build_max_heap(heap)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    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:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[-1]
    a.pop()
    build_max_heap(a)
    return max


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


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print(extract_max(heap))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))

Submission status: Time Limit Exceeded

Solution code:
def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:  # ???????????????
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print(extract_max(heap))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
A = []
H = 0
def maxHeapify(A,i):
    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:
        A[i-1], A[largest-1] = A[largest-1], A[i-1]
        maxHeapify(A,largest)

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

def Insert(key):
    global H
    H += 1
    A.append(-1111)
    heapIncreaseKey(A,H,key)

def heapIncreaseKey(A,i,key):
    if key < A[i-1]:
        return
    A[i-1] = key
    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 //= 2

def heapExtractMax(A):
    global H
    if H < 1:
        return
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    A.pop()
    maxHeapify(A,1)
    return maxv


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

Submission status: Time Limit Exceeded

Solution code:
import sys

def parent(i, n):
    tmp = i/2
    if tmp <=0 or tmp>=n: return None
    else: return tmp

def left(i, n):
    tmp = 2*i
    if tmp>=n: return None
    else: return tmp
    
def right(i, n):
    tmp = 2*i+1
    if tmp>=n: return None
    else: return tmp

def maxheapify(A, i):
    n = len(A)
    f = [0,0,0]
    f[0] = A[i]

    l=left(i, n)
    if l == None:
        f[1]=None
    else:
        f[1]=A[l]
    
    r=right(i,n)
    if r == None:
        f[2]=None
    else:
        f[2]=A[r]
        
    tmp = f.index(max(f))
    if tmp == 1:
        tmp=A[i]
        A[i]=A[l]
        A[l]=tmp
        maxheapify(A, l)
    elif tmp == 2:
        tmp=A[i]
        A[i]=A[r]
        A[r]=tmp
        maxheapify(A, r)

def buildmaxheap(A):
    for i in range(1,len(A))[::-1]:
        maxheapify(A,i)

def maxheapinsert(A, key):
    A.append(None)
    heapincreasekey(A,len(A)-1,key)

def heapincreasekey(A,i,key):
    if 1<i<len(A) and A[i]!=None and key<A[i]:
        print "error"
        return
    A[i]=key
    tmp=parent(i, len(A)-1)
    while tmp!=None and A[tmp]<A[i]:
        tmp2=A[tmp]
        A[tmp]=A[i]
        A[i]=tmp2
        i = tmp
        tmp = parent(i, len(A)-1)

def heapextractmax(A):
    if len(A)<=1:
        print "error"
        quit
    m=A[1]
    tmp=A.pop()
    if len(A)>1:
        A[1]=tmp
        maxheapify(A,1)
    return m
    
x=[0]
while True:
    text = raw_input()
    if text == "end": break
    elif text[0] == "i": maxheapinsert(x, int(text[7:]))
    elif text[0] == "e": print heapextractmax(x)

Submission status: Time Limit Exceeded

Solution code:
import sys

def parent(i, n):
    tmp = i/2
    if tmp <=0 or tmp>=n: return None
    else: return tmp

def left(i, n):
    tmp = 2*i
    if tmp>=n: return None
    else: return tmp
    
def right(i, n):
    tmp = 2*i+1
    if tmp>=n: return None
    else: return tmp

def maxheapify(A, i):
    n = len(A)
    f = [0,0,0]
    f[0] = A[i]

    l=left(i, n)
    if l == None:
        f[1] = None
    else:
        f[1] = A[l]
    
    r = right(i,n)
    if r == None:
        f[2] = None
    else:
        f[2] = A[r]
        
    tmp = f.index(max(f))
    if tmp == 1:
        A[i], A[l] = A[l], A[i]
        maxheapify(A, l)
    elif tmp == 2:
        A[i], A[r] = A[r], A[i]
        maxheapify(A, r)

def buildmaxheap(A):
    i = len(A) - 1
    while i>0:
        maxheapify(A,i)
        i = i - 1

def maxheapinsert(A, key):
    A.append(None)
    heapincreasekey(A, len(A)-1, key)

def heapincreasekey(A,i,key):
    lena=len(A)
    if 1<i<lena and A[i]!=None and key<A[i]:
        print "error"
        return
    A[i] = key
    tmp = parent(i, lena-1)
    while tmp!=None and A[tmp]<A[i]:
        A[tmp], A[i] = A[i], A[tmp]
        i = tmp
        tmp = parent(i, len(A)-1)

def heapextractmax(A):
    if len(A)<=1:
        print "error"
        quit
    m = A[1]
    tmp = A.pop()
    if len(A)>1:
        A[1]=tmp
        maxheapify(A, 1)
    return m
    
x=[0]
while True:
    text = raw_input()
    if text == "end": break
    elif text[0] == "i": maxheapinsert(x, int(text[7:]))
    elif text[0] == "e": print heapextractmax(x)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def max_heapify(a, i, heap_size):
    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, heap_size)


def max_heap_insert(a, key, heap_size):
    heap_size[0] += 1
    a[heap_size[0]] =  -1-maxint
    heap_increase_key(a, key, heap_size[0])


def heap_increase_key(a, key, i):
    if key < a[i]:
        raise ValueError('new key less current key')
    a[i] = key
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2


def heap_extract_max(a, heap_size):
    if heap_size[0] < 1:
        raise ValueError('heap under flow')
    max = a[1]
    a[1] = a[heap_size[0]]
    heap_size[0] -= 1
    max_heapify(a, 1, heap_size[0])
    return max


heap = [-1-maxint] * 2000001
heap_size = [1]
for cmd in stdin:
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert 0 <= key <= 2000000000
        max_heap_insert(heap, key, heap_size)
    elif cmd.startswith('ex'):
        print(heap_extract_max(heap, heap_size))
    elif cmd.startswith('en'):
        break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint

MININT = -1 - maxint


def max_heapify(a, i, heap_size):
    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, heap_size)


def max_heap_insert(a, key, heap_size):
    heap_size[0] += 1
    a[heap_size[0]] = MININT
    heap_increase_key(a, key, heap_size[0])


def heap_increase_key(a, key, i):
    #if key < a[i]:
        #raise ValueError('new key less current key')
    a[i] = key
    half = i // 2
    while i > 1 and a[half] < a[i]:
        a[i], a[half] = a[half], a[i]
        i = i // 2
        half = i // 2


def heap_extract_max(a, heap_size):
    #if heap_size[0] < 1:
        #raise ValueError('heap under flow')
    max = a[1]
    a[1] = a[heap_size[0]]
    heap_size[0] -= 1
    max_heapify(a, 1, heap_size[0])
    return max


heap = [MININT] * 2000001
heap_size = [1]
for cmd in stdin:
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert 0 <= key <= 2000000000
        max_heap_insert(heap, key, heap_size)
    elif cmd.startswith('ex'):
        print(heap_extract_max(heap, heap_size))
    elif cmd.startswith('en'):
        break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint

MININT = -1 - maxint


def max_heapify(a, i, heap_size):
    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, heap_size)


def max_heap_insert(a, key, heap_size):
    heap_size[0] += 1
    a[heap_size[0]] = MININT
    heap_increase_key(a, key, heap_size[0])


def heap_increase_key(a, key, i):
    #if key < a[i]:
        #raise ValueError('new key less current key')
    a[i] = key
    half = i // 2
    while i > 1 and a[half] < a[i]:
        a[i], a[half] = a[half], a[i]
        i = i // 2
        half = i // 2


def heap_extract_max(a, heap_size):
    #if heap_size[0] < 1:
        #raise ValueError('heap under flow')
    max = a[1]
    a[1] = a[heap_size[0]]
    heap_size[0] -= 1
    max_heapify(a, 1, heap_size[0])
    return max


heap = [MININT] * 2000001
heap_size = [1]
for cmd in stdin:
    if cmd[0] == 'i':
        key = int(cmd[7:])
        #assert 0 <= key <= 2000000000
        max_heap_insert(heap, key, heap_size)
    elif cmd[1] == 'x':
        print(heap_extract_max(heap, heap_size))
    elif cmd[1] == 'n':
        break

Submission status: Memory Limit Exceeded

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!')
    # the root of the heap is always the largest
    heap_max = heap_array[1]

    # move new data to heap root
    heap_array[1] = heap_array[heap_length]
    heap_length -= 1

    # print
    heap_array.pop()
    print(heap_max)
    max_heapify(1)
    # assert len(heap_array) == heap_length + 1
    return heap_max


def insert(data):
    global heap_length
    heap_length += 1
    heap_array.append(-1)
    # 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()

    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 = [-1], 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: Memory Limit Exceeded

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

import sys


def max_heapify(index):
    global heap_length
    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!')
    # the root of the heap is always the largest
    heap_max = heap_array[1]

    # move new data to heap root
    heap_array[1] = heap_array[heap_length]
    heap_length -= 1

    # print
    heap_array.pop()
    print(heap_max)
    max_heapify(1)
    # assert len(heap_array) == heap_length + 1
    return heap_max


def insert(data):
    global heap_length
    heap_length += 1
    heap_array.append(-1)
    # 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()

    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 = [-1], 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: Memory Limit Exceeded

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

import sys
import heapq as hp


def heap_push(value):
    hp.heappush(heap_array, -1 * value)
    return None


def heap_pop():
    print(-1 * hp.heappop(heap_array))


def action(_command, _content):
    if _command.startswith('in'):
        heap_push(int(_content))
    elif _command.startswith('ex'):
        heap_pop()

    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 = []
    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: Memory Limit Exceeded

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

import sys
import heapq as hp


def heap_push(value):
    hp.heappush(heap_array, -1 * value)
    return None


def heap_pop():
    print(-1 * hp.heappop(heap_array))


def action(_command, _content):
    if _command.startswith('in'):
        heap_push(int(_content))
    elif _command.startswith('ex'):
        heap_pop()

    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 = []
    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: Memory Limit Exceeded

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

import sys
import heapq as hp


# def heap_push(value):
#     hp.heappush(heap_array, -1 * value)
#     return None
#
#
# def heap_pop():
#     print(-1 * hp.heappop(heap_array))
#
#
# def action(_command, _content):
#     if _command.startswith('in'):
#         heap_push(int(_content))
#     elif _command.startswith('ex'):
#         heap_pop()
#
#     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 = []
    for each in command_list:
        command, content = each[0], each[-1]
        if command not in allowed_commands:
            raise SystemExit('Illegal command!')
        if command.startswith('in'):
            hp.heappush(heap_array, -1 * int(content))
        elif command.startswith('ex'):
            print(-1 * hp.heappop(heap_array))

Submission status: Memory Limit Exceeded

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

import sys


def max_heapify(index):
    # global heap_length
    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!')
    # the root of the heap is always the largest
    heap_max = heap_array[1]

    # move new data to heap root
    heap_array[1] = heap_array[heap_length]
    heap_length -= 1

    # print
    heap_array.pop()
    print(heap_max)
    max_heapify(1)
    # assert len(heap_array) == heap_length + 1
    return heap_max


def insert(data):
    global heap_length
    heap_length += 1
    heap_array.append(-1)
    # 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):
    if _command.startswith('in'):
        insert(int(each[7:]))
    elif _command.startswith('ex'):
        extract()

    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 = [-1], 0
    for each in _input:
        # command, content = each[0], each[-1]
        # if command not in allowed_commands:
        #     raise SystemExit('Illegal command!')

        action(each)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  9 13:21:18 2018
ALDS1-9c
@author: maezawa
"""
import heapq as hq
        
h = []

while True:
    s = input()
    if s == 'end':
        break
    if s == 'extract':
        print(-hq.heappop(h))
        continue
    opcode, operand = s.split()
    data = int(operand)
    if opcode == 'insert':
        hq.heappush(h, -data)

Submission status: Accepted

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

from heapq import heappush, heappop

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

que=[]
while True:
    instr=input()
    if instr.startswith('insert'):
        _,n=instr.split()
        heappush(que, -int(n))
    elif instr.startswith('extract'):
        print(-heappop(que))
    else:
        break

Submission status: Accepted

Solution code:
import heapq
q=[]
bool1=True
while bool1:
  n=input()
  if n=="end":
    bool1=False
    break
  elif n=="extract":
    i=heapq.heappop(q)
    print(-int(i))
  else:
    a,b=n.split()
    b=int(b)
    heapq.heappush(q,-b)

Submission status: Accepted

Solution code:
import heapq
Q,s = [],[]
flag = 0
while(flag==0):
  c = input()
  if c == "end":
    break
  elif c == "extract":
    print(heapq.heappop(Q) * (-1))
  else:
    s = c.split()
    heapq.heappush(Q, int(s[1])*(-1))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys

if __name__ == '__main__':
	pq = []
	while True:
		cmd = sys.stdin.readline()
		if cmd.strip() == 'end': break
		elif cmd.startswith('insert'):
			_, val = cmd.split()
			heappush(pq, -int(val))
		else:
			print -(heappop(pq))

Submission status: Accepted

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


import heapq

def main():
    heap = []
    while True:
        line = readline()
        if line[2] == 't':
            print(heapq.heappop(heap)[1])
        elif line[2] == 's':
            n = int(line.split()[1])
            heapq.heappush(heap, (-n, n))
        else:
            break

main()