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:
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def left(self, i):
        return 2 * i

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

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

    def extract(self):
        if self.h < 1:
            return -1
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -1
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [-1] * 2000000 * 1
    x = MaxHeap(a, 0)
    while True:
        com = input().rstrip()
        if com == "end":
            break
        elif com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("extract"):
            print(x.extract())

Submission status: Time Limit Exceeded

Solution code:
INFTY = 1<<30
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

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

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

    def extract(self):
        if self.h < 1:
            return -INFTY
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -INFTY
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [None] * (2000000 + 1)
    x = MaxHeap(a, 0)
    while True:
        com = input().rstrip()
        if com == "end":
            break
        elif com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("extract"):
            print(x.extract())

Submission status: Time Limit Exceeded

Solution code:
import sys
INFTY = 1<<30
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

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

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

    def extract(self):
        if self.h < 1:
            return -INFTY
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -INFTY
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [None] * (2000000 + 1)
    x = MaxHeap(a, 0)
    ret = [None] * (2000000 + 1)
    i = 0
    coms = sys.stdin.readlines()
    for com in coms:
        if com[0] == "i":
            k = int(com.split()[1])
            x.insert(k)
        elif com[0:2] == "ex":
            ret[i] = x.extract()
            i += 1
        else:
            sys.stdout.write("\n".join([str(s) for s in ret[:i]]))
            print()

Submission status: Time Limit Exceeded

Solution code:
import sys
INFTY = 1<<30
a = [None] * (2000000 + 1)
h = 0
ret = [None] * (2000000 + 1)
i = 0

def left(i):
    return 2 * i

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

def maxHeapify(i):
    global a, h
    l = left(i)
    r = right(i)
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

coms = sys.stdin.readlines()
for com in coms:
    if com[0] == "i":
        k = int(com.split()[1])
        insert(k)
    elif com[0:2] == "ex":
        ret[i] = extract()
        i += 1
    else:
        sys.stdout.write("\n".join([str(s) for s in ret[:i]]))
        print()

Submission status: Time Limit Exceeded

Solution code:
import sys
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = [] 

def maxHeapify(i):
    global a, h
    l = 2 * i
    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
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print("\n".join([str(s) for s in ret]))
        # print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = deque([]) 

def maxHeapify(i):
    global a, h
    l = 2 * i
    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
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print("\n".join([str(s) for s in list(ret)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = [] 

def maxHeapify(i):
    global a, h
    l = 2 * i
    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
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print(*ret, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = []

def maxHeapify(i):
    global a, h
    l = 2 * i
    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
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

i = 0
for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract())
    else:
        sys.stdout.writelines("\n".join([str(s) for s in ret]))
        print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = deque([])

def maxHeapify(i):
    global a, h
    l = 2 * i
    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
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

i = 0
for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract())
    else:
        sys.stdout.writelines("\n".join([str(s) for s in ret]))
        print()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, exit
 
def max_heapify(a, i):
    heap_size = a[0]
 
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
 
 
def main():
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
 
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            print(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            exit(0)
 
 
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, exit
  
def max_heapify(a, i):
    heap_size = a[0]
  
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
  
  
def main():
    ret = []
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
  
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            ret.append(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            stdout.writelines("\n".join([str(s) for s in ret]))
            print()
            exit(0)
  
  
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

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


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


def insert(S, k):
    S.append(k)
    build_max_heap(S)


def extract(S):
    res = S.popleft()
    build_max_heap(S)
    return res

S = deque()
while True:
    cmd = input().split()
    if cmd[0] == "insert":
        insert(S, int(cmd[1]))
    elif cmd[0] == "extract":
        print(extract(S))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

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


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


def extract(S):
    build_max_heap(S)
    return S.popleft()

S = deque()
while True:
    cmd = input().split()
    if cmd[0] == "insert":
        S.append(int(cmd[1]))
    elif cmd[0] == "extract":
        print(extract(S))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import heapq


hq = []
while True:
    cmd = input().split()
    if cmd[0] == "insert":
        heapq.heappush(hq, -int(cmd[1]))
    elif cmd[0] == "extract":
        heapq.heapify(hq)
        print(-heapq.heappop(hq))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
class PQueue:
    def __init__(self):
        self.keys = []
        self.size = 0
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < self.size and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < self.size and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

    def insert(self, key):
        i = self.size
        self.size += 1
        self.keys.append(key)
        parent = (i - 1) // 2
        while i > 0 and self.keys[parent] < self.keys[i]:
            self.keys[i], self.keys[parent] = self.keys[parent], self.keys[i]
            i = parent
            parent = (parent - 1) // 2

    def heapExtraMax(self):
        max_key = self.keys[0]
        if self.size > 1:
            self.keys[0] = self.keys.pop()
            self.size -= 1
            if self.size > 1:
                self.maxHeapify(0)
        else:
            del self.keys[0]
            self.size -= 1
        return max_key


S = PQueue()

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[:2] == 'ex':
        m_k = S.heapExtraMax()
        print(m_k)
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

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

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        return max_key


S = PQueue()

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[:2] == 'ex':
        m_k = S.heapExtraMax()
        print(m_k)
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

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

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        return max_key


S = PQueue()

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        m_k = S.heapExtraMax()
        print(m_k)
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

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

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        print(max_key)


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        S.heapExtraMax()
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

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

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        return max_key


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        ans.append(S.heapExtraMax())
    else:
        pass

print(*ans, sep = '\n')

Submission status: Time Limit Exceeded

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

def heapInsert(keys, key):
    i = len(keys)
    keys.append(key)
    parent = (i - 1) // 2
    while i > 0 and keys[parent] < keys[i]:
        keys[i], keys[parent] = keys[parent], keys[i]
        i = parent
        parent = (parent - 1) // 2

def heapMaxPop(keys):
    max_key = keys[0]
    if len(keys) > 1:
        keys[0] = keys.pop()
    else:
        del keys[0]
    maxHeapify(keys, 0)
    print(max_key)


S = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapInsert(S, k)
    elif x[1] == 'x':
        heapMaxPop(S)
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:
def maxHeapify(i):
    l = i * 2 + 1
    r = i * 2 + 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(largest)

def heapInsert(key):
    i = len(A)
    A.append(key)
    parent = (i - 1) // 2
    while i > 0 and A[parent] < A[i]:
        A[i], A[parent] = A[parent], A[i]
        i = parent
        parent = (parent - 1) // 2

def heapMaxPop():
    max_key = A[0]
    if len(A) > 1:
        A[0] = A.pop()
    else:
        del A[0]
    maxHeapify(0)
    print(max_key)


A = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapInsert(k)
    elif x[1] == 'x':
        heapMaxPop()
    else:
        pass

Submission status: Time Limit Exceeded

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

def maxHeapify(A, i):
    n = len(A)-1
    l = 2*i
    r = 2*i+1
    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 buildMaxHeap(A):
    n = len(A)-1
    for i in range(n/2, 0, -1):
        maxHeapify(A, i)

A = [0]
while True:
    line = map(str, raw_input().split())
    if line[0] == "insert":
        A.append(int(line[1]))
        buildMaxHeap(A)
    elif line[0] == "extract":
        print A.pop(1)
        buildMaxHeap(A)
    if line[0] == "end":
        break

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(A, i):
	l = i * 2 
	r = i * 2 + 1
	largest = i
	if l < len(A):
		if A[l] > A[largest]:
			largest = l
	if r < len(A):
		if 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(int(len(A) / 2), 0, -1):
		max_heapify(A, i)
def insert(A, k):
	A.append(k)
def extract_max(A):
	build_max_heap(A)
	k = A.pop(1)
	return k

A = [None]
while True:
	o = list(map(str, input().split()))
	if o[0] == "insert":
		insert(A, int(o[1]))
	elif o[0] == "extract":
		print(extract_max(A))
	else:
		break

Submission status: Time Limit Exceeded

Solution code:

def insert(A, k):
	i = len(A)
	A.append(k)
	while i != 0:
		j = int((i - 1) / 2)
		if A[j] < A[i]:
			A[i], A[j] = A[j], A[i]
		i = j
def extract_max(A):
	k = A[0]
	A[0] = A[-1]
	A.pop()
	n = len(A)
	p = 0
	while True:
		c = 2 * p + 1
		if c >= n:
			break
		if c < n - 1 and A[c] < A[c + 1]:
			c += 1
		if A[p] < A[c]:
			A[p], A[c] = A[c], A[p]
		p = c
	return k

A = []
while True:
	o = list(map(str, input().split()))
	if o[0] == "insert":
		insert(A, int(o[1]))
	elif o[0] == "extract":
		print(extract_max(A))
	else:
		break

Submission status: Time Limit Exceeded

Solution code:
import heapq
A = []
while True:
	o = list(map(str, input().split()))
	if o[0] == "insert":
		heapq.heappush(A, -int(o[1]))
	elif o[0] == "extract":
		print(-heapq.heappop(A))
	else:
		break

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    now = len(S) - 1
    while True:
        p = parent(now)
        if p < 0:
            break
        elif S[now] > S[p]:
            S[now], S[p] = S[p], S[now]
        else:
            now = p

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

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    now = len(S) - 1
    while True:
        p = parent(now)
        if p < 0:
            break
        elif S[now] > S[p]:
            S[now], S[p] = S[p], S[now]
        else:
            now = p

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

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    now = len(S) - 1
    while True:
        p = parent(now)
        if p < 0:
            break
        elif S[now] > S[p]:
            S[now], S[p] = S[p], S[now]
        else:
            now = p

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

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)