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(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, n)
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: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
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, n)
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 = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        print(extractMax(A))
    else:
       insert(A, int(s[7:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    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)
    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)
    return ans
A = []
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        n -= 1
        print(extractMax(A))
    else:
        n += 1
        insert(A, int(s[7:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    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)
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    if len(S) == 1:
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    maxHeapify(S, 0)
    return ans
A = []
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        n -= 1
        print(extractMax(A))
    else:
        n += 1
        insert(A, int(s[7:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    S.append(k)
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    n -= 1
    maxHeapify(S, 0)
    return ans
A = []
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        print(extractMax(A))
    else:
        n += 1
        insert(A, int(s[7:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        print(extractMax(A))
    else:
        insert(A, int(s[7:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
while True:
    s = readline()
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print(extractMax(A))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print(extractMax(A))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    i = 0
    while True:
        l = i * 2 + 1
        r = i * 2 + 2
        if l >= n:
            break
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            i = largest
        else:
            break
    return ans
A = [0] * 2000000
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print(extractMax(A))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect, insort_left, insort
A = []
for s in sys.stdin:
    if s[2] == "s":
        insort(A, int(s[7:]))
    elif s[2] == "t":
        print(A.pop())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect, insort_left, insort
A = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        insort(A, int(s[7:]))
    elif s[2] == "t":
        S.append(A.pop())
    else:
        break
print(*S, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect, insort_left, insort
A = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        insort(A, int(s[7:]))
    elif s[2] == "t":
        S.append(A.pop())
    else:
        break
print("\n".join(map(str, S)))

Submission status: Time Limit Exceeded

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

Solution code:
import sys
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 e in sys.stdin:
 if'i'==e[0]:
  H+=1;A+=[int(e[7:])];k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  print(A[1])
  if H>1:A[1]=A.pop()
  H-=1;h(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
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]*2000001
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  print(A[1])
  if H>1:A[1]=A[H]
  H-=1;h(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
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]*2000001
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  print(A[1]);H-=1
  if H:A[1]=A[H+1];h(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
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]*2000001
o=[]
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  o+=[A[1]];H-=1
  if H:A[1]=A[H+1];h(1)
 else:print('\n'.join(map(str,o)))

Submission status: Time Limit Exceeded

Solution code:
import sys
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]*2000001
o=[]
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  o+=[A[1]];H-=1
  if H:A[1]=A[H+1];h(1)
print('\n'.join(map(str,o)))

Submission status: Time Limit Exceeded

Solution code:
import sys
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]*2000001
o=''
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  o+=f'{A[1]}\n';H-=1
  if H:A[1]=A[H+1];h(1)
print(o[:-1])

Submission status: Time Limit Exceeded

Solution code:
def insert(a, data):
    a.append(data)
    heapinc(a, len(a)-1)

def heapinc(a, index):
    parent = (index - 1) // 2
    if parent >= 0:
        if a[parent] < a[index]:
            memo = a[parent]
            a[parent] = a[index]
            a[index] = memo
            heapinc(a, parent)

def extract(a):
    root = a[0]
    a[0] = a[-1]
    del a[-1]
    maxheapify(a, 0)
    return root

def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2

    if r < len(a):
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if a[r] > a[largest]:
            largest = r

        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

    elif l < len(a):
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

a = []
for i in range(2000000001):
    com = input().split()
    if com[0] == 'insert':
        insert(a, int(com[1]))
    elif com[0] == 'extract':
        print(extract(a))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def insert(a, data):
    a.append(data)
    heapinc(a, len(a)-1)

def heapinc(a, index):
    parent = (index - 1) // 2
    if parent >= 0:
        if a[parent] < a[index]:
            memo = a[parent]
            a[parent] = a[index]
            a[index] = memo
            heapinc(a, parent)

def extract(a):
    root = a[0]
    a[0] = a[-1]
    del a[-1]
    maxheapify(a, 0)
    return root

def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2

    if r < len(a):
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if a[r] > a[largest]:
            largest = r

        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

    elif l < len(a):
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

a = []
while 1:
    com = input().split()
    if com[0] == 'insert':
        insert(a, int(com[1]))
    elif com[0] == 'extract':
        print(extract(a))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys


class QueueEmptyError(Exception):
    pass


class PriorityQueue:
    def __init__(self):
        self._nodes = []
        self.size = 0

    def add(self, v):
        self._nodes.append(v)
        self.size += 1

        self._build_up(self.size-1)

    def extract(self):
        if self.size == 0:
            raise QueueEmptyError()

        node = self._nodes[0]
        self.size -= 1
        last = self._nodes.pop()
        if self.size > 0:
            self._nodes[0] = last
            self._build_down(0)

        return node

    def _build_down(self, i):
        top = i
        left = (i+1) * 2 - 1
        right = (i+1) * 2
        if left < self.size and self._nodes[left] > self._nodes[top]:
            top = left
        if right < self.size and self._nodes[right] > self._nodes[top]:
            top = right

        if top > i:
            self._nodes[top], self._nodes[i] = \
                self._nodes[i], self._nodes[top]
            self._build_down(top)

    def _build_up(self, i):
        if i == 0:
            return

        parent = (i-1) // 2
        if self._nodes[parent] < self._nodes[i]:
            self._nodes[parent], self._nodes[i] = \
                    self._nodes[i], self._nodes[parent]
            self._build_up(parent)


def run():
    q = PriorityQueue()

    for line in sys.stdin:
        if line.startswith("insert"):
            q.add(int(line[7:]))
        elif line.startswith("extract"):
            print(q.extract())
        elif line.startswith("end"):
            break
        else:
            ValueError("invalid command")


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys


class QueueEmptyError(Exception):
    pass


class PriorityQueue:
    def __init__(self):
        self._nodes = []

    def add(self, v):
        self._nodes.append(v)
        i = len(self._nodes) - 1
        while i > 0:
            parent = (i-1) // 2
            vp, vi = self._nodes[parent], self._nodes[i]
            if vp < vi:
                self._nodes[parent], self._nodes[i] = vi, vp
                i = parent
            else:
                break

    def extract(self):
        size = len(self._nodes) - 1
        if size < 0:
            raise QueueEmptyError()

        node = self._nodes[0]
        last = self._nodes.pop()
        if size > 0:
            self._nodes[0] = last
            i = 0
            while i < size // 2:
                top = i
                left = (i+1) * 2 - 1
                right = (i+1) * 2
                vi = self._nodes[top]
                vt = vi
                if left < size:
                    vl = self._nodes[left]
                    if vl > vt:
                        top = left
                        vt = vl
                if right < size:
                    vr = self._nodes[right]
                    if vr > vt:
                        top = right
                        vt = vr

                if top > i:
                    self._nodes[top], self._nodes[i] = vi, vt
                    i = top
                else:
                    break

        return node


def run():
    q = PriorityQueue()

    for line in sys.stdin:
        if line.startswith("i"):
            q.add(int(line[7:]))
        elif line.startswith("ex"):
            print(q.extract())
        elif line.startswith("end"):
            break
        else:
            ValueError("invalid command")


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
d = []
while True:
    s = input()
    if s[2] == "d":
        break
    elif s[0] == "i":
        d.append(int(s[7:]))
    else:
        print(d.pop(d.index(max(d))))

Submission status: Time Limit Exceeded

Solution code:
def insert(k):
    a.append(-1)
    heap_increasekey(a, len(a) - 1, k)
def heap_increasekey(a, i, k):
    a[i] = k
    while i > 1 and a[int(i / 2)] < a[i]:
        a[i], a[int(i / 2)] = a[int(i / 2)], a[i]
        i = int(i / 2)
def heap_extractmax(a):
    m = a[1]
    a[1] = a[-1]
    a.pop()
    max_heapify(a, 1)
    return m

def max_heapify(a, i):
    l = 2 * i
    r = 2 * i + 1
    largest = l if l < len(a) and a[l] > a[i] else i
    if r < len(a) and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[largest], a[i] = a[i], a[largest]
        max_heapify(a, largest)
        
a = [0]
while True:
    s = input()
    if s[2] == "d":
        break
    elif s[0] == "i":
        insert(int(s[7:]))
    else:
        print(heap_extractmax(a))

Submission status: Time Limit Exceeded

Solution code:
class PriorityQueue:
    def __init__(self):
        self.nodes = []

    def max_heapify(self, i):
        if i >= len(self.nodes): return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < len(self.nodes) and self.nodes[i] < self.nodes[left]: largest = left
        if right < len(self.nodes) and self.nodes[largest] < self.nodes[right]: largest = right

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

    def extract_max(self):
        if len(self.nodes) < 1: return
        max = self.nodes[0]
        self.nodes[0] = self.nodes[-1]
        self.nodes.pop(-1)
        self.max_heapify(0)
        return max

    def insert(self, key):
        self.nodes.append(key)
        i = len(self.nodes)-1
        par = lambda i: (i-1)//2
        while i > 0 and self.nodes[par(i)] < self.nodes[i]:
            self.nodes[i], self.nodes[par(i)] = self.nodes[par(i)], self.nodes[i]
            i = par(i)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

pq = PriorityQueue()
while True:
    op = input().split(' ')
    if op[0] == 'insert':
        pq.insert(int(op[1]))
    elif op[0] == 'extract':
        print(pq.extract_max())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

class PriorityQueue:
    def __init__(self):
        self.nodes = []

    def max_heapify(self, i):
        if i >= len(self.nodes): return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < len(self.nodes) and self.nodes[i] < self.nodes[left]: largest = left
        if right < len(self.nodes) and self.nodes[largest] < self.nodes[right]: largest = right

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

    def extract_max(self):
        if len(self.nodes) < 1: return
        max = self.nodes[0]
        self.nodes[0] = self.nodes[-1]
        self.nodes.pop(-1)
        self.max_heapify(0)
        return max

    def insert(self, key):
        self.nodes.append(key)
        i = len(self.nodes)-1
        par = lambda i: (i-1)//2
        while i > 0 and self.nodes[par(i)] < self.nodes[i]:
            self.nodes[i], self.nodes[par(i)] = self.nodes[par(i)], self.nodes[i]
            i = par(i)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

pq = PriorityQueue()

for line in sys.stdin.readlines():
    op = line.strip().split(' ')
    if op[0] == 'insert':
        pq.insert(int(op[1]))
    elif op[0] == 'extract':
        print(pq.extract_max())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

class PriorityQueue:
    def __init__(self):
        self.nodes = []

    def max_heapify(self, i):
        if i >= len(self.nodes): return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < len(self.nodes) and self.nodes[i] < self.nodes[left]: largest = left
        if right < len(self.nodes) and self.nodes[largest] < self.nodes[right]: largest = right

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

    def extract_max(self):
        if len(self.nodes) < 1: return
        max = self.nodes[0]
        self.nodes[0] = self.nodes[-1]
        self.nodes.pop(-1)
        self.max_heapify(0)
        return max

    def insert(self, key):
        self.nodes.append(key)
        i = len(self.nodes)-1
        par = lambda i: (i-1)//2
        while i > 0 and self.nodes[par(i)] < self.nodes[i]:
            self.nodes[i], self.nodes[par(i)] = self.nodes[par(i)], self.nodes[i]
            i = par(i)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

pq = PriorityQueue()

lines = sys.stdin.readlines()
for line in lines:
    op = line.strip().split(' ')
    if op[0] == 'insert':
        pq.insert(int(op[1]))
    elif op[0] == 'extract':
        print(pq.extract_max())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

class PriorityQueue:
    def __init__(self):
        self.nodes = []
        self.num = 0

    def max_heapify(self, i):
        if i >= self.num: return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < self.num and self.nodes[i] < self.nodes[left]: largest = left
        if right < self.num and self.nodes[largest] < self.nodes[right]: largest = right

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

    def extract_max(self):
        if self.num < 1: return
        max = self.nodes[0]
        self.nodes[0] = self.nodes[-1]
        self.nodes.pop(-1)
        self.num -= 1
        self.max_heapify(0)
        return max

    def insert(self, key):
        self.nodes.append(key)
        self.num += 1
        i = self.num-1
        par = lambda i: (i-1)//2
        while i > 0 and self.nodes[par(i)] < self.nodes[i]:
            self.nodes[i], self.nodes[par(i)] = self.nodes[par(i)], self.nodes[i]
            i = par(i)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

pq = PriorityQueue()

lines = sys.stdin.readlines()
for line in lines:
    op = line.strip().split(' ')
    if op[0] == 'insert':
        pq.insert(int(op[1]))
    elif op[0] == 'extract':
        print(pq.extract_max())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    q = []
    heapq.heapify(q)
    while True:
        s = input().split()
        if s[0] == 'end':
            break
        elif s[0] == 'insert':
            heapq.heappush(q, (-int(s[1]), int(s[1])))
        else:
            p = heapq.heappop(q)
            print(p[1])

if __name__ == '__main__':
    main()

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
        # node_list[i], node_list[2*i+1] = node_list[2*i+1], node_list[i]
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2
        # node_list[i], node_list[2*i+2] = node_list[2*i+2], node_list[i]

    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)
    n = len(node_list)
    for i in range(n//2, -1, -1):
        maxHeapify(i, node_list)

def extract_heap(node_list):
    print(node_list[0])
    pop = node_list.pop()
    n = len(node_list)
    if n != 0:
        node_list[0] = pop
    for i in range(n//2, -1, -1):
        maxHeapify(i, 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:
# -*- coding: utf-8 -*-
INF = -10**10
queue = [-1]


def insert(queue, key):
    h = len(queue) - 1
    queue.append(INF)
    heap_increase_key(queue, h + 1, key)


def heap_increase_key(queue, i, key):
    if key < queue[i]:
        raise ValueError('The new key is smaller than the present key')
    queue[i] = key
    while i > 1 and queue[i // 2] < queue[i]:
        queue[i], queue[i // 2] = queue[i // 2], queue[i]
        i = i // 2


def extract_max(queue):
    h = len(queue) - 1
    if h < 1:
        raise TypeError('Heap underflowed')
    max = queue[1]
    queue[1] = queue.pop()
    max_heapify(queue, 1)

    return max


def max_heapify(queue, i):
    h = len(queue) - 1
    l = 2 * i
    r = 2 * i + 1
    if l <= h and queue[l] > queue[i]:
        largest = l
    else:
        largest = i
    if r <= h and queue[r] > queue[largest]:
        largest = r

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


if __name__ == '__main__':
    import sys
    ords = [line.strip().split() for line in sys.stdin]

    for ord in ords:
        if len(ord) > 1:
            ord, key = ord[0], int(ord[1])
        else:
            ord = ord[0]
        if ord[0] == 'i':
            insert(queue, key)
        elif len(ord) == 7:
            print(extract_max(queue))
        else:
            break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
INF = -10**10
queue = [-1]


def insert(queue, key):
    h = len(queue) - 1
    queue.append(INF)
    heap_increase_key(queue, h + 1, key)


def heap_increase_key(queue, i, key):
    if key < queue[i]:
        raise ValueError('The new key is smaller than the present key')
    queue[i] = key
    while i > 1 and queue[i // 2] < queue[i]:
        queue[i], queue[i // 2] = queue[i // 2], queue[i]
        i = i // 2


def extract_max(queue):
    h = len(queue) - 1
    if h < 1:
        raise TypeError('Heap underflowed')
    max = queue[1]
    queue[1] = queue.pop()
    h -= 1

    i = 1
    while True:
        l = 2 * i
        r = 2 * i + 1
        if l <= h and queue[l] > queue[i]:
            largest = l
        else:
            largest = i
        if r <= h and queue[r] > queue[largest]:
            largest = r

        if largest != i:
            queue[i], queue[largest] = queue[largest], queue[i]
            i = largest
        else:
            break

    return max


if __name__ == '__main__':
    import sys
    ords = [line.strip().split() for line in sys.stdin]

    for ord in ords:
        if len(ord) > 1:
            ord, key = ord[0], int(ord[1])
        else:
            ord = ord[0]
        if ord[0] == 'i':
            insert(queue, key)
        elif len(ord) == 7:
            print(extract_max(queue))
        else:
            break