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 dw_heap(A,i,length):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if l < length and A[l] > A[largest]: largest = l
        if r < length and A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest


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


if __name__=='__main__':
    hp = [None]*(2*10**6)
    hp[0] = 2*10**9 + 1
    i = 1
    j = -1 
    while True:
        op = input() 
        if   op[0] != 'i': break
        hp[i] = int(op[7:])
        i += 1
    if op[2] != 'd':
        for k in range(i//2,0,-1): dw_heap(hp,k,i)
    while True:
        if   op[2] == 'd': break
        if   op[0] == 'i':
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        else:# extract
            hp[j] = hp[1]
            hp[1],hp[i-1] = hp[i-1],hp[1]
            dw_heap(hp,1,i-1)
            i -= 1
            j -= 1
        op = input() 
    print(*hp[:j:-1],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def upheap(a,i):
    while i > 0:
        p = (i+1)/2-1
        if a[p] < a[i]:
            a[p],a[i]=a[i],a[p]
        i = p
def heap_insert(a,v):
    a.append(v)
    upheap(a,len(a)-1)
def extract(a):
    ret = a[0]
    a[0],a[len(a)-1]=a[len(a)-1],a[0]
    del a[len(a)-1]
    downheap(a,0)
    return ret
def downheap(a,i):
    lid = (i+1)*2-1
    rid = (i+1)*2
    maxc = -1
    if lid < len(a):
        maxc = lid
    if rid < len(a):
        if maxc == -1 or a[maxc] < a[rid]:
            maxc = rid
    if maxc != -1:
        if a[i] < a[maxc]:
            a[i],a[maxc]=a[maxc],a[i]
            downheap(a,maxc)


a = []
ret = []
while True:
    op = raw_input()
    if op[0] == 'e' and op[1] == 'n':
        break
    elif op[0] == 'i':
        num = int(op.split(' ')[1])
        heap_insert(a,num)
    else:
        ret.append(extract(a))

for r in ret:
    print r

Submission status: Time Limit Exceeded

Solution code:
import bisect
queue = []
targ = input()
while targ != "end":
    targ = targ.split(' ')
    if targ[0] == "insert":
        queue.insert(bisect.bisect_left(queue,int(targ[1])),int(targ[1]))
    else:
        temp = queue.pop()
        print(temp)
    targ = input()

Submission status: Time Limit Exceeded

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

    def insert(self, num):
        self.heap.append(num)
        
        i = len(self.heap) - 1
        while (i-1)//2 >= 0:
            if self.heap[i] <= self.heap[(i-1)//2]:
                break
            self.heap[i], self.heap[(i-1)//2] = self.heap[(i-1)//2], self.heap[i]
            i = (i-1)//2


    def extract(self):
        ret = self.heap[0]
        last_element = self.heap.pop()

        if len(self.heap) != 0:
            self.heap[0] = last_element
        else:
            self.heap.append(last_element)

        i = 0
        while 2 * i + 1 < len(self.heap):
            l = 2 * i + 1
            r = 2 * i + 2

            pos = l
            if len(self.heap) > r and self.heap[r] > self.heap[l]:
                pos = r

            if self.heap[pos] <= self.heap[i]:
                break

            self.heap[pos], self.heap[i] = self.heap[i], self.heap[pos]
            i = pos
        return ret

pq = PriorityQueue()
while True:
    command = input().split()
    if len(command) == 1 and command[0] == "extract":
        print(pq.extract())
    elif len(command) == 1 and command[0] == "end":
        break
    else:
        c, num = command[0], int(command[1])
        pq.insert(num)

Submission status: Time Limit Exceeded

Solution code:
import math
def parent(i):
    return math.floor(i / 2)

def get_largest(i):
    global SIZE
    l = i << 1
    r = l + 1
    largest = None
    if l <= SIZE and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= SIZE and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(i):
    largest = get_largest(i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(x)

def extract():
    global SIZE
    m = A[1]
    A[1] = A[SIZE]
    SIZE -= 1
    max_heapify(1)
    return m

def increase_key(i, key):
    if key < A[i]:
        raise NameError('key is less than A[i]')
    A[i] = key
    while 1 < i and A[parent(i)] < A[i]:
        tmp = A[i]
        A[i] = A[parent(i)]
        A[parent(i)] = tmp
        i = parent(i)

def insert_key(key):
    global SIZE
    SIZE += 1
    A.append(None)
    A[SIZE] = -1
    increase_key(SIZE, key)

inp = input()
A = [None]
SIZE = 0

loop =  inp[0:2] is not 'en'

while loop:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(extract())
    elif inp[0] == 'i':
        insert_key(int(inp[7:]))
    inp = input()

Submission status: Time Limit Exceeded

Solution code:
import math
def parent(i):
    return math.floor(i / 2)

def get_largest(i):
    l = i << 1
    r = l + 1
    largest = None
    size = len(A) - 1
    if l <= size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= size and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(i):
    largest = get_largest(i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(x)

def extract():
    m = A[1]
    A[1] = A[-1]
    A.pop()
    max_heapify(1)
    return m

def insert_key(key):
    A.append(key)
    i = len(A) - 1
    while 1 < i and A[parent(i)] < A[i]:
        tmp = A[i]
        A[i] = A[parent(i)]
        A[parent(i)] = tmp
        i = parent(i)

inp = input()
A = [None]

while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(extract())
    elif inp[0] == 'i':
        insert_key(int(inp[7:]))
    inp = input()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

def parent(i):
    return math.floor(i / 2)

def get_largest(i):
    l = i << 1
    r = l + 1
    largest = None
    size = len(A) - 1
    if l <= size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= size and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(i):
    largest = get_largest(i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(x)

def extract():
    m = A[1]
    A[1] = A[-1]
    A.pop()
    max_heapify(1)
    return m

def insert_key(key):
    A.append(key)
    i = len(A) - 1
    while 1 < i and A[parent(i)] < A[i]:
        tmp = A[i]
        A[i] = A[parent(i)]
        A[parent(i)] = tmp
        i = parent(i)

inp = input()
A = deque()
A.append(0)

while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(extract())
    elif inp[0] == 'i':
        insert_key(int(inp[7:]))
    inp = input()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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

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

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


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

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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


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

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

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

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

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


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

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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

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

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


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

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#coding:UTF-8
class Queue:
    def __init__(self):
        self.max=0
        self.q=list()

def insert(S,k):
    S.q.append(k)
    if len(S.q)==1:
        S.max=k
    else:
        if S.max<k:
            S.max=k
            
def extractMax(S):
    print(S.max)
    S.q.remove(S.max)
    if len(S.q)!=0:
        nmax=S.q[0]
        for i in range(1,len(S.q)):
            if nmax<S.q[i]:
                nmax=S.q[i]
        S.max=nmax
    
    
def PQ(S,lineList):
    for i in range(len(lineList)):
        if lineList[i]=="extract":
            extractMax(S)
        else:
            k=int(lineList[i].split(" ")[1])
            insert(S,k)

if __name__=="__main__":
    S=Queue()
    lineList=[]
    while 1:
        line=input()
        if line=="end":
            break
        lineList.append(line)
    PQ(S,lineList)

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

Solution code:
from heapq import heappush, heappop

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

Submission status: Time Limit Exceeded

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

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


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

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

    def insert(self, x):
        self.pqueue.append(x)

    def extractMax(self):
        max_value = max(self.pqueue)
        self.pqueue.pop(self.pqueue.index(max_value))
        return max_value


if __name__ == '__main__':

    pqueue = PQueue()

    line = input()
    while line != 'end':
        if line.split()[0] == 'insert':
            pqueue.insert(int(line.split()[1]))
        elif line.split()[0] == 'extract':
            print(pqueue.extractMax())
        line = input()

Submission status: Time Limit Exceeded

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

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


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

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

    def insert(self, x):
        self.pqueue.append(x)

    def extractMax(self):
        max_value = max(self.pqueue)
        self.pqueue.pop(self.pqueue.index(max_value))
        return max_value


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

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

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

Submission status: Time Limit Exceeded

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

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


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

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

    def insert(self, x):
        self.pqueue.append(x)

    def extractMax(self):
        max_value = max(self.pqueue)
        self.pqueue.pop(self.pqueue.index(max_value))
        return max_value


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

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

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

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

Submission status: Time Limit Exceeded

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

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


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

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

    def insert(self, x):
        self.pqueue.append(x)

    def extractMax(self):
        return self.pqueue.pop(self.pqueue.index(max(self.pqueue)))


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def insertHeap(H, A, key):
    A.append(key)
    i = H + 1

    while i > 1 and A[i] > A[i // 2]:
        A[i], A[i // 2] = A[i // 2], A[i]
        i //= 2

def popHeap(H, A):
    max_ = A[1]

    A[1] = A[H]
    A.pop()
    maxHeapify(H - 1, A, 1)

    return max_

def maxHeapify(H, A, i):
    left = 2 * i
    right = 2*i + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right <= H and A[right] > A[largest]:
        largest = right

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

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

H = 0
A = [None]

while 1:
    cmd = sys.stdin.readline().split()
    # print(A, file=sys.stderr)

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

    if cmd[0] == 'extract':
        print(popHeap(H, A))
        H -= 1
    else:
        insertHeap(H, A, int(cmd[1]))
        H += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

def insertHeap(H, A, key):
    A[H] = key
    i = H

    while i > 1 and A[i] > A[i // 2]:
        A[i], A[i // 2] = A[i // 2], A[i]
        i //= 2

def popHeap(H, A):
    max_ = A[1]

    A[1] = A[H]
    maxHeapify(H - 1, A, 1)

    return max_

def maxHeapify(H, A, i):
    left = 2 * i
    right = 2*i + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right <= H and A[right] > A[largest]:
        largest = right

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

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

MAX_ = 2 * 10**6
H = 0
A = [None] * (MAX_ + 1)

while 1:
    cmd = sys.stdin.readline().split()
    # print(A, file=sys.stderr)

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

    if cmd[0] == 'extract':
        print(popHeap(H, A))
        H -= 1
    else:
        H += 1
        insertHeap(H, A, int(cmd[1]))

Submission status: Time Limit Exceeded

Solution code:
a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':a+=[int(b[7:])]
    else:a.sort();print(a[-1]);a.pop()

Submission status: Time Limit Exceeded

Solution code:
a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':a+=[int(b[7:])]
    else:c=max(a);print(c);a.remove(c)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

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

        return MAX

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


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

Submission status: Time Limit Exceeded

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

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

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

A = [0]
cmd = input()
while cmd != "end":
  if cmd == "extract":
    if len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, 1)
  else:
    cmd, k = cmd.split()
    if cmd == "insert":
      A.append(int(k))
      build_max_heap(A)
  cmd = input()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

A = [0]

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

Submission status: Time Limit Exceeded

Solution code:
heap = [0]
NIL = -1


def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


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


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


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

    return max


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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

NIL = -100000000


def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


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


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


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

    return max


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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
 
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
 
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)

A = [None]
L = input()
while L !="end":
    L = L.split()
    if L[0] == "insert":
        A.append(int(L[1]))
    else:
        buildmaxHeap(len(A) - 1, A)
        print(str(A[1]))
        A = [None] + A[2:]
    L = input()

Submission status: Time Limit Exceeded

Solution code:
def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
 
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
 
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)

A = [None]
L = input()
while L !="end":
    L = L.split()
    if L[0] == "insert":
        A.append(int(L[1]))
        buildmaxHeap(len(A) - 1, A)
    else:
        print(str(A[1]))
        A = [None] + A[2:]
        buildmaxHeap(len(A) - 1, A)
    L = input()

Submission status: Time Limit Exceeded

Solution code:
def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
  
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
  
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)
 
A = [None]
import sys
for x in sys.stdin.readlines():
    if x[0] == 'i':
        A.append(int(x[7:]))
    elif x[1] == 'x':
        buildmaxHeap(len(A) - 1, A)
        print(str(A[1]))
        A = [None] + A[2:]
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
from math import floor

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

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

    if r < H and A[r] > A[largest] :
        largest = r
    #print('largest',largest)
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        maxheapfi(largest)
    
def extract():
    global H
    global A
    if H < 0 : return -1000000
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    maxheapfi(0)
    #print(32,A)
    return maxv

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

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