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:
import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)
    
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
_input = sys.stdin.readlines()
H = 0
A = [0]
def main():
    for l in _input:
        if l[0] == "e":
            if l[1] == "n":
                #end
                return
            else:
                #print(A)
                extract(A)
        else:
            #insert k
            k = int(l.split()[1])
            A.append(k)
            build_max_heap(A)
        #print(A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

def extract(A):
    out = A[1]
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    return out

_input = sys.stdin.readlines()
A = [0]

def main():
    out = []
    for l in _input:
        if l[0] == "e":
            if l[1] == "n":
                #end
                print(*out, sep = "\n")
                return
            else:
                #print(A)
                out.append(extract(A))
        else:
            #insert k
            k = int(l.split()[1])
            A.append(k)
            build_max_heap(A)
        #print(A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

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

_input = sys.stdin.readlines()
A = [0]

#@profile
def main():
    out = []
    for l in _input:
        if l[0] == "e":
            if l[1] == "n":
                #end
                print(*out, sep = "\n")
                return
            else:
                build_max_heap(A)
                #print(A)
                out.append(extract(A))
        else:
            #insert k
            k = int(l.split()[1])
            A.append(k)
            #build_max_heap(A)
        #print(A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

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

_input = sys.stdin.readlines()
A = [0]
out=[]

#@profile
def main():
    for l in _input:
        if l[0] == "e":
            if l[1] == "n":
                #end
                print(*out, sep = "\n")
                return
            else:
                build_max_heap(A)
                #print(A)
                out.append(extract(A))
        else:
            #insert k
            k = int(l.split()[1])
            A.append(k)
            #build_max_heap(A)
        #print(A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

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

_input = sys.stdin.readlines()
A = [0]
out=[]

#@profile
def main():
    for l in _input:
        if l[0] == "i":
            #insert k
            k = int(l.split()[1])
            A.append(k)
            #build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(*out, sep = "\n")
            return
        else:
            build_max_heap(A)
            #print(A)
            out.append(extract(A))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

#@profile
def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

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

_input = sys.stdin.readlines()
A = [0]
out=[]

#@profile
def main():
    for l in _input:
        if l[0] == "i":
            #insert k
            A.append(int(l.split()[1]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(*out, sep = "\n")
            return
        else:
            #build_max_heap(A)
            #print(A)
            out.append(extract(A))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

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

#@profile
def main():
    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:
                print(A.pop())
            #extract(A)
            else:
                print(A[1])
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    q = deque()
    H = 0
    while(True):
        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,H)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    q = []
    H = 0
    while(True):
        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[0]
            q[0] = q[-1]
            q.pop()
            H -= 1
            if H >= 2:
                maxHeapify(q,1,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)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    q = [0]*int(2e+6)
    H = 0
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q[H]=int(cmd[1])
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q[0]
            q[0] = q[H-1]
            H -= 1
            if H >= 2:
                maxHeapify(q,1,H)
        else:
            break

def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            A[p-1], A[i-1] = A[i-1], A[p-1]
            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:
        A[i-1], A[largest-1] = A[largest-1], A[i-1]
        maxHeapify(A,largest,H)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    q = [0]*int(2e+6)
    H = 0
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q[H]=int(cmd[1])
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q[0]
            q[0] = q[H-1]
            H -= 1
            if H >= 2:
                maxHeapify(q,1,H)
        else:
            break
 
def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            A[p-1], A[i-1] = A[i-1], A[p-1]
            increase(A,p)
             
def maxHeapify(A,i,H):
    l = 2*i
    r = 2*i+1
    largest = i
    if l <= H :
        if A[l-1] > A[i-1]:
            largest = l
    if r <= H:
        if 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,H)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Solution code:
def swap(A, x, y):
    i = A[x]
    A[x] = A[y]
    A[y] = i

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

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

def  maxHeapify(A, i, H):
    l = left(i)
    r = right(i)
#    print("i:{} left:{} right:{} MAX:{}".format(i,l,r,H))
    #  ????????????????????????????????§???????????§????????????????????¶
    if l < H and A[l] > A[i]:
#        print("i[{}]:{} left[{}]:{}".format(i,A[i],l,A[l]))
        largest = l
    else:
        largest = i
    if r < H and A[r] > A[largest]:
#        print("i[{}]:{} left[{}]:{}".format(i,A[i],l,A[l]))
        largest = r

    if largest != i: #// i ???????????????????????§????????´???
        swap(A, i, largest) # ??????
        maxHeapify(A, largest, H) # ?????°??????????????????

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

def main():

    """ ????????? """
    end = False
    S = []
    
    while end != True:
        cmd = input()
#        print("cmd:{} S:{}".format(cmd,S))
        if cmd == "extract":
            buildMaxHeap(S, len(S))
            print(S[0])
            S = S[1:]
        elif cmd == "end":
            end = True
        elif cmd[0] == "i":
            S.append(int(cmd[7:]))

if __name__ == '__main__':
    main()

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:
        r = (i+1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
        else:
            lv = 0
        if r < H:
            rv = A[r]
        else:
            rv = 0
        if lv == 0 and rv == 0:
            break
        elif A[i] < lv and lv > rv:
            A[l] = A[i]
            A[i] = lv
            i = l
        elif A[i] < rv:
            A[r] = A[i]
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(A,n):
    A.append(n)
    i = len(A) - 1
    while i > 0:
        p = int((i + 1) / 2) - 1
        if A[p] < A[i]: # ???????????§??????
            x = A[p]
            A[p] = A[i]
            A[i] = x
            i = p
        else:
            break

def main():

    """ ????????? """
    end = False
    S = []
    
    while end != True:
        cmd = input()
#        print("cmd:{} S:{}".format(cmd,S))
        if cmd == "extract":
            a = extractMax(S)
            print(a)
            
        elif cmd == "end":
            end = True

        elif cmd[0] == "i":
            insert(S,int(cmd[7:]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
class Node():
    def __init__(self, id, key, parent, left=None, right=None):
        self.id = id
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
    def show(self):
        print 'node %d: key = %d,' % (self.id, self.key),
        if self.parent:
            print 'parent key = %d,' % self.parent, 
        if self.left:
            print 'left key = %d,' % self.left,
        if self.right:
            print 'right key = %d,' % self.right,
        print ''

def calcParent(id, T):
    if id == 1:
        return None
    else:
        return T[int(id/2)].key

def calcLeft(id, T):
    if 2 * id < len(T) + 1:
        return T[2 * id].key
    return None

def calcRight(id, T):
    if 2 * id < len(T):
        return T[2 * id + 1].key
    return None

def updateHeap(T):
    for i in T.keys():
        if not T[i].left:
            T[i].left = calcLeft(i, T)
        if not T[i].right:
            T[i].right = calcRight(i, T)
    return T
            
def maxHeapify(T, i):
    val_i, val_l, val_r = T[i].key, None, None
    if T[i].left:
        val_l = T[i*2].key
    if T[i].right:
        val_r = T[i*2+1].key
    if val_l and val_l > val_i:
        largest = val_l
    else:
        largest = val_i
    if val_r and val_r > largest:
        largest = val_r
    if largest != val_i:
        T[i].key = largest
        if T[i].parent:
            if T[int(i/2)].left == val_i:
                T[int(i/2)].left = largest
            else:
                T[int(i/2)].right = largest
        if largest == val_l:
            T[i*2].key = val_i
            T[i*2].parent = largest
            T[i].left = val_i
            T = maxHeapify(T, i*2)
        else:
            T[i*2+1].key = val_i
            T[i*2+1].parent = largest
            T[i].right = val_i
            T = maxHeapify(T, i*2+1)
    return T

def extract(T, i):
    val_l, val_r = None, None
    if T[i].left:
        val_l = T[i*2].key
    if T[i].right:
        val_r = T[i*2+1].key
    if val_l > val_r:
        T[i].key = val_l
        if T[i].parent:
            if T[i].key == T[int(i/2)].left:
                T[int(i/2)].left = val_l
            else:
                T[int(i/2)].right = val_l
        if i*2 < len(T):
            T[i*2+1].parent = val_l
        if i*2 < len(T) + 1:
            T = extract(T, i*2)
    else:
        T[i].key = val_r
        if T[i].parent:
            if T[i].key == T[int(i/2)].left:
                T[int(i/2)].left = val_r
            else:
                T[int(i/2)].right = val_r
        if i*2 < len(T):
            T[i*2].parent = val_r
            T = extract(T, i*2+1)
    return T

T = {}
this_id = 0
while True:
    command = raw_input().split()
    this_id += 1 
    if command[0] == 'insert':
        T[len(T) + 1] = Node(this_id, int(command[1]), calcParent(this_id, T))
        T = updateHeap(T)
        for i in range(int(this_id/2), 0, -1):
            T = maxHeapify(T, i)
    elif command[0] == 'extract':
        print T[1].key
        T = extract(T, 1)
        continue
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def insert(S, k):
    S.append(k)

def extractMax(S):
    ret = S[0]
    S[:] = S[1:]
    return ret

def maxHeapify(A, i):
    l = 2 * i + 1
    r = 2 * i + 2
    if l < len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)

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

S = []
i = input()
while i != 'end':    
    if i == 'extract':
        buildMaxHeap(S)
        print(extractMax(S))
    else:
        op, k = i.split()
        insert(S, int(k))
    i = input()

Submission status: Time Limit Exceeded

Solution code:
def heapify(values):
  n = len(values)
  for i in range(1,n):
    upheap(values,i)
    print(' '.join(map(str, values)))

def upheap(values, i):
  while parent(i) >= 0:
    if values[i] > values[parent(i)]:
      values[i], values[parent(i)] = values[parent(i)], values[i]
      i = parent(i)
    else:
      break

def pop(values):
  ret = values[0]
  values[0], values[len(values)-1] = values[len(values)-1], values[0]
  del values[len(values)-1]
  downheap(values)
  return ret

def push(values, x):
  values.append(x)
  upheap(values, len(values)-1)

def downheap(values):
  i = 0
  while left(i) < len(values) or right(i) < len(values):
    l = left(i)
    r = right(i)
    if l >= len(values):
      m = r
    elif r >= len(values):
      m = l
    else:
      m = r
      if values[l] > values[r]:
        m = l
    if values[i] < values[m]:
      values[m], values[i] = values[i], values[m]
    i = m

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

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

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

values = []
while True:
  line = input()
  if line.startswith('end'):
    break
  elif line.startswith('extract'):
    print(pop(values))
  elif line.startswith('insert'):
    num = int(line.split(' ')[1])
    push(values, num)

Submission status: Time Limit Exceeded

Solution code:
def heapify(values):
  n = len(values)
  for i in range(1,n):
    upheap(values,i)
    print(' '.join(map(str, values)))

def upheap(values, i):
  while parent(i) >= 0:
    if values[i] > values[parent(i)]:
      values[i], values[parent(i)] = values[parent(i)], values[i]
      i = parent(i)
    else:
      break

def pop(values):
  ret = values[0]
  values[0], values[len(values)-1] = values[len(values)-1], values[0]
  del values[len(values)-1]
  downheap(values)
  return ret

def push(values, x):
  values.append(x)
  upheap(values, len(values)-1)

def downheap(values):
  i = 0
  while left(i) < len(values) or right(i) < len(values):
    l = left(i)
    r = right(i)
    if l >= len(values):
      m = r
    elif r >= len(values):
      m = l
    else:
      m = r
      if values[l] > values[r]:
        m = l
    if values[i] < values[m]:
      values[m], values[i] = values[i], values[m]
    else:
      break
    i = m

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

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

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

values = []
while True:
  line = input()
  if line.startswith('end'):
    break
  elif line.startswith('extract'):
    print(pop(values))
  elif line.startswith('insert'):
    num = int(line.split(' ')[1])
    push(values, num)

Submission status: Time Limit Exceeded

Solution code:
a = []
while True:
    inp = input().split()
    if inp[0] == "insert":
        a.append(int(inp[1]))
    elif inp[0] == "extract":
        a.sort()
        print(a.pop())
    else:
        break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections
commands = []
while True:
    line = input()
    if line == 'end': break
    commands.append(line)



queue = collections.deque()
for line in commands:
    pair = line.split()
    if len(pair) < 2: #extract
        big = max(queue)
        print(big)
        queue.remove(big)
    else: #insert
        num = int(pair[1])
        queue.append(num)

Submission status: Time Limit Exceeded

Solution code:
import heapq
commands = []
while True:
    line = input()
    if line == 'end': break
    commands.append(line)


queue = []
heapq.heapify(queue)
for line in commands:
    pair = line.split()
    if len(pair) < 2: #extract
        big = heapq.nlargest(1,queue)[0]
        queue.remove(big)
        print(big)
    else: #insert
        num = int(pair[1])
        heapq.heappush(queue,num)

Submission status: Time Limit Exceeded

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]

    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]:
            return
        self[i] = key
        while i > 1 and self[parent(i)] < self[i]:
            self[i], self[parent(i)] = self[parent(i)], self[i]
            i = parent(i)

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = A[self.H]
        self.pop()
        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)

    def print(self):
        print(" ".join(map(str, self)))


if __name__ == '__main__':

    A = MaxHeap()
    while True:
        #A.print()
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            break

Submission status: Time Limit Exceeded

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]

    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]:
            return
        self[i] = key
        while i > 1 and self[parent(i)] < self[i]:
            pi = parent(i)
            self[i], self[pi] = self[pi], self[i]
            i = pi

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = A[self.H]
        self.pop()
        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)

    def print(self):
        print(" ".join(map(str, self)))


if __name__ == '__main__':

    A = MaxHeap()
    while True:
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            break

Submission status: Time Limit Exceeded

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]

    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]:
            return
        self[i] = key
        while i > 1 and self[parent(i)] < self[i]:
            pi = parent(i)
            self[i], self[pi] = self[pi], self[i]
            i = pi

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = self.pop()
        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()
    while True:
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            break

Submission status: Time Limit Exceeded

Solution code:
class PriorityQueue:

    def __init__(self):
        self.q = {}

    def insert(self, k):
        self.q[k] = self.q.get(k, 0) + 1

    def extractMax(self):
        result = max(self.q)
        self.q[result] -= 1
        if self.q[result] == 0:
            del self.q[result]
        return result


if __name__ == '__main__':

    q = PriorityQueue()
    while True:
        al = input().split()

        if al[0] == "insert":
            q.insert(int(al[1]))
        elif al[0] == "extract":
            print(q.extractMax())
        elif al[0] == "end":
            break