Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Priority Queue

  A priority queue is a data structure which maintains a set $S$ of elements, each of with an associated value (key), and supports the following operations:

$insert(S, k)$: insert an element $k$ into the set $S$

$extractMax(S)$: remove and return the element of $S$ with the largest key

  Write a program which performs the $insert(S, k)$ and $extractMax(S)$ operations to a priority queue $S$.
  The priority queue manages a set of integers, which are also keys for the priority.

Input

  Multiple operations to the priority queue $S$ are given. Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.

The input ends with "end" operation.

Output

For each "extract" operation, print the element extracted from the priority queue $S$ in a line.

Constraints

The number of operations $\leq 2,000,000$

$0 \leq k \leq 2,000,000,000$

Sample Input 1

insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end

Sample Output 1

8
10
11
2



Sample input:
insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end


Sample output:
8
10
11
2

Submission status: Time Limit Exceeded

Solution code:
import sys

A = [0]*2000000
H = 0

def maxHeapify(i):
    global H, A
    l = (i+1)*2-1
    r = (i+1)*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:  # i の子の方が値が大きい場合
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(largest) #  再帰的に呼び出し


while True:
    com = sys.stdin.readline()
    if com[2] == 'd':   break
    if com[0] == 'i':
        _, arg = com.strip().split()
        A[H] = int(arg)
        H+=1
        i=H-1
        parent = (i-1)//2
        if parent<0: continue
        while A[parent]<A[i]:
            A[parent], A[i] = A[i], A[parent]
            if parent<=0: break
            i, parent = parent, (parent-1)//2
        
    else: # extract
        print(A[0])
        A[0] = A[H-1]
        maxHeapify(0)
        H-=1

Submission status: Time Limit Exceeded

Solution code:
import sys

A = [0]*2000000
H = 0

def maxHeapify(i):
    global A
    l = (i+1)*2-1
    r = l+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:  # i の子の方が値が大きい場合
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(largest) #  再帰的に呼び出し


while True:
    com = sys.stdin.readline()
    if com[0] == 'i':
        _, arg = com.split()
        A[H] = int(arg)
        H += 1
        i = H-1
        parent = (i-1)//2
        while parent>=0 and A[parent]<A[i]:
            A[parent], A[i] = A[i], A[parent]
            i, parent = parent, (parent-1)//2

    elif com[1]=='x': # extract
        sys.stdout.write(str(A[0]))
        sys.stdout.write('\n')
        A[0] = A[H-1]
#        maxHeapify(0)
        # 左の子、自分、右の子で値が最大のノードを選ぶ
        largest = 0
        if 1 < H and A[1] > A[0]:            largest = 1
        if 2 < H and A[2] > A[largest]:      largest = 2

        if largest > 0:  # i の子の方が値が大きい場合
            A[0], A[largest] = A[largest], A[0]
            maxHeapify(largest) #  再帰的に呼び出し

        H-=1

    else: break

Submission status: Time Limit Exceeded

Solution code:
def get_parent(A, i):
    if i == 1:
        return None
    else:
        return i // 2

def get_left(A, i):
    if len(A) > 2 * i:
        return 2 * i
    else:
        return None

def get_right(A, i):
    if len(A) > 2 * i + 1:
        return 2 * i + 1
    else:
        return None

A = [-1] * 2000000
H = 0

def insert(A, key):
    global H
    H += 1
    A[H] = key
    i = H
    while i > 1:
        # print(i)
        parent = get_parent(A, i)
        if parent is None:
            break
        if A[parent] < A[i]:
            # print('swap', i, parent, A[i], A[parent])
            tmp = A[i]
            A[i] = A[parent]
            A[parent] = tmp
            i = parent
        else:
            break

def max_heapfy(A, i):
    left = get_left(A, i)
    right = get_right(A, i)
    largest = i
    if left and A[left] > A[i]:
        largest = left
    if right and A[right] > A[largest]:
        largest = right
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        max_heapfy(A, largest)

def extract_max(A):
    global H
    max_value = A[1]
    A[1] = A[H]
    A[H] = -1
    H -= 1
    max_heapfy(A, 1)
    return max_value

# Heap heap ヒープの実装はここを参考にした
# http://ikapblg.blog.fc2.com/blog-entry-57.html

def print_heap(A):
    for index, elem in enumerate(A):
        if index == 0:
            continue
        if elem == -1:
            break
        print(elem)

while True:
    line = input().split()
    if line[0] == 'insert':
        insert(A, int(line[1]))
        # print(A)
    elif line[0] == 'extract':
        max_value = extract_max(A)
        print(max_value)

    else:
        # print('end:')
        # print_heap(A)
        break

Submission status: Time Limit Exceeded

Solution code:
class PriorityQueue:
    INIT_VALUE = -1
    MAX_SIZE = 2000001

    def __init__(self):
        self.heap = [PriorityQueue.INIT_VALUE] * PriorityQueue.MAX_SIZE
        self.size = 0

    def insert(self, key):
        self.size += 1
        self.heap[self.size] = key
        i = self.size
        while i > 1:
            parent_index = i // 2
            if parent_index == 0:
                break
            if self.heap[parent_index] < self.heap[i]:
                tmp = self.heap[i]
                self.heap[i] = self.heap[parent_index]
                self.heap[parent_index] = tmp
                i = parent_index
            else:
                break

    def extract_max(self):
        max_value = self.heap[1]
        self.heap[1] = self.heap[self.size]
        self.heap[self.size] = PriorityQueue.INIT_VALUE
        self.size -= 1
        self.max_heapfy(1)
        return max_value

    def max_heapfy(self, i):
        left = self.get_left(i)
        right = self.get_right(i)
        largest = i
        if left and self.heap[left] > self.heap[i]:
            largest = left
        if right and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != i:
            tmp = self.heap[i]
            self.heap[i] = self.heap[largest]
            self.heap[largest] = tmp
            self.max_heapfy(largest)

    def print_queue(self):
        for i in range(1, self.size + 1):
            print(self.heap[i])

    def get_left(self, i):
        if 2 * i <= self.size:
            return 2 * i
        else:
            None

    def get_right(self, i):
        if 2 * i + 1 <= self.size:
            return 2 * i + 1
        else:
            None

q = PriorityQueue()
while True:
    line = input().split()
    if line[0] == 'insert':
        q.insert(int(line[1]))
        # print(A)
    elif line[0] == 'extract':
        max_value = q.extract_max()
        print(max_value)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
class PriorityQueue:
    INIT_VALUE = -1
    MAX_SIZE = 2000001
    def __init__(self):
        self.heap = [PriorityQueue.INIT_VALUE]*(PriorityQueue.MAX_SIZE + 1)
        self.size = 0
    
    def insert(self, k):
        self.size += 1
        self.heap[self.size] = k
        # up heap
        tidx = self.size
        while tidx > 0:
            pidx = tidx // 2
            if pidx == 0: break
            t = self.heap[tidx]
            p = self.heap[pidx]
            if t > p:
                self.heap[pidx],self.heap[tidx] = t,p
                tidx = pidx
            else: break

    def extract_max(self):
        pv = self.heap[1]
        self.heap[1], self.heap[self.size] = self.heap[self.size], PriorityQueue.INIT_VALUE
        self.size -= 1
        # down heap
        tidx = 1
        while tidx > 0:
            t = self.heap[tidx]
            lidx = tidx * 2
            ridx = lidx + 1
            l = self.heap[lidx] if lidx <= PriorityQueue.MAX_SIZE else -1
            r = self.heap[ridx] if ridx <= PriorityQueue.MAX_SIZE else -1
            if l == -1 and r == -1: break
            if l > r and l > t:
                self.heap[tidx],self.heap[lidx] = l,t
                tidx = lidx
            elif r >= l and r > t:
                self.heap[tidx],self.heap[ridx] = r,t
                tidx = ridx
            else: break
        return pv

op = input().split()
pq = PriorityQueue()
while not op[0] == 'end':
    if op[0] == 'insert':
        pq.insert(int(op[1]))
    elif op[0] == 'extract':
        v = pq.extract_max()
        print(v)
    op = input().split()

Submission status: Time Limit Exceeded

Solution code:
Q,s = [],[]
flag = 0
while(flag==0):
  c = input()
  if c == "end":
    break
  elif c == "extract":
    print(Q.pop(0))
  else:
    s = c.split()
    Q.append(int(s[1]))
    Q.sort(reverse = True)

Submission status: Time Limit Exceeded

Solution code:
Q,s = [],[]
flag = 0
while(flag==0):
  c = input()
  if c == "end":
    break
  elif c == "extract":
    Q.sort(reverse = True)
    print(Q.pop(0))
  else:
    s = c.split()
    Q.append(int(s[1]))

Submission status: Time Limit Exceeded

Solution code:
def swap(queue, i, j):
    a = queue[i]
    queue[i] = queue[j]
    queue[j] = a
    return queue

def enqueue(queue, data):
    queue.append(data)
    i = len(queue) - 1
    while i > 0:
        if queue[(i - 1) / 2] < queue[i]:
            queue = swap(queue, (i - 1) / 2, i)
            i = (i - 1) / 2
        else:
            return
    return

def dequeue(queue):
    queue = swap(queue, 0, -1)
    d = queue.pop()
    i = 0
    l = len(queue) - 1
    while l > 2 * i:
        if queue[i] < queue[2 * i + 1]:
            if l > 2 * i + 1:
                if queue[2 * i + 2] < queue[2 * i + 1]:
                    queue = swap(queue, 2 * i + 1, i)
                    i = 2 * i + 1
                else:
                    queue = swap(queue, 2 * i + 2, i)
                    i = 2 * i + 2
            else:
                queue = swap(queue, 2 * i + 1, i)
                i = 2 * i + 1
        elif l > 2 * i + 1:
            if queue[i] < queue[2 * i + 2]:
                queue = swap(queue, 2 * i + 2, i)
                i = 2 * i + 2
            else:
                return d
        else:
            return d
    return d

queue = []

while 1:
    word = raw_input()
    if word == "end":
        break
    elif word == "extract":
        print dequeue(queue)
    else:
        enqueue(queue, int(word.split()[1]))

Submission status: Time Limit Exceeded

Solution code:
def parent(i):return (i - 1) // 2
def left(i):return  2 * i + 1
def right(i):return  2 * i + 2
def max_heapify(a, i):
    l = left(i)
    r = right(i)
    largest = l if  l < len(a) and a[l] > a[i] else i
    largest = r if  r < len(a) and a[r] > a[largest] else largest
    
    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 max_heap_insert(a, key):
    a.append(key)
    heap_increase_key(a)
def heap_increase_key(a):
    i = len(a) - 1
    while i > 0 and a[parent(i)] < a[i]:
        a[i], a[parent(i)] = a[parent(i)], a[i]
        i = parent(i)
def heap_extract_max(a):
    if  len(a)  == 0:
        raise Exception
    max_heap = a[0]
    a[0] = a[-1]
    a.pop(-1)
    max_heapify(a, 0)
    return max_heap

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def maxHeapify(A, i):
    l = 2*i
    r = 2*i+1
    
    if l <= (len(A)-1) and A[l] > A[i]:
        largest = l
    else:
        largest = i
        
    if r <= (len(A)-1) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)
        
def buildMaxHeap(A):
    for i in range((len(A)-1)/2,0,-1):
        maxHeapify(A,i)

A = [0]
while True:
    order = raw_input().split()
    if order[0] == "insert":
        A.append(int(order[1]))
    elif order[0] == "extract":
        print A.pop(1)
    else: # end
        break
    buildMaxHeap(A)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def maxHeapify(A, i):
    l = 2*i
    r = 2*i+1
    
    if l <= (len(A)-1) and A[l] > A[i]:
        largest = l
    else:
        largest = i
        
    if r <= (len(A)-1) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)
        
def buildMaxHeap(A):
    for i in xrange((len(A)-1)/2,0,-1):
        maxHeapify(A,i)

A = [0]
while True:
    order = raw_input().split()
    if order[0][0] == "i":
        A.append(int(order[1]))
    elif order[0][1] == "x":
        buildMaxHeap(A)
        print A.pop(1)
    else: # end
        break

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def maxHeapify(A, i):
    l = 2*i
    r = 2*i+1
    
    if l <= (len(A)-1) and A[l] > A[i]:
        largest = l
    else:
        largest = i
        
    if r <= (len(A)-1) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)
        
def buildMaxHeap(A):
    for i in xrange((len(A)-1)/2,0,-1):
        maxHeapify(A,i)

A = [0]
while True:
    order = raw_input().split()
    if order[0] == "insert":
        A.append(int(order[1]))
    elif order[0] == "extract":
        buildMaxHeap(A)
        print A.pop(1)
    else: # end
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

heap = []
while True:
	input_line = sys.stdin.readline()
	input_line = input_line.strip().split(' ')
	if input_line[0][0] == 'i' :
		heapq.heappush(heap,-int(input_line[1]))
		heapq.heapify(heap)
	elif input_line[0][1] == 'x' :
		print(-int(heapq.heappop(heap)))
	else :
		break

Submission status: Time Limit Exceeded

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C
# Priority Quue
# Result:
import sys

def insert(heap, val):
    hsize = len(heap)
    heap.insert(hsize, val)
    ci = hsize
    pi = hsize / 2
    while pi != 0 and heap[ci] > heap[pi]:
        tmp = heap[ci]
        heap[ci] = heap[pi]
        heap[pi] = tmp
        ci = pi
        pi = pi / 2

def extract(heap):
    max_ = heap[1]
    if len(heap) == 2: # -1 and one value
        heap.pop()
    else:
        heap[1] = heap.pop()
        max_heapify(heap, len(heap) - 1, 1)
    return max_

def max_heapify(ary, nary, i):
    left = i * 2
    right = left + 1
    if left <= nary and ary[left] > ary[i]:
        largest = left
    else:
        largest = i
    if right <= nary and ary[right] > ary[largest]:
        largest = right
    if largest != i:
        tmp = ary[i]
        ary[i] = ary[largest]
        ary[largest] = tmp
        max_heapify(ary, nary, largest)


_heap = [-1]
for line in sys.stdin.readlines():
    ops = line.rstrip().split(' ')
    if ops[0] == 'insert':
        insert(_heap, int(ops[1]))
    elif ops[0] == 'extract':
        v = extract(_heap)
        print v
    elif ops[0] == 'end':
        break
    else:
        assert True

Submission status: Time Limit Exceeded

Solution code:
from heapq import *

PQ = []
heapify(PQ)

while True:
    line = input().split()
    if line[0] == 'insert':
        heappush(PQ, -int(line[1]) )
    elif line[0] == 'extract':
        print(-heappop(PQ))
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
A=[]
while True:
	a=raw_input().split()
	if a[0]=='insert':
		A.append(int(a[1]))
	elif a[0]=='extract':
		print max(A)
		A.remove(max(A))
	else: break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
def left(i):
    return i * 2

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

def parent(i):
    return i // 2

def heap_increase_key(A, key):
    i = len(A) - 1
    A[i] = key
    while i > 1 and A[parent(i)] < A[i]:
        A[i], A[parent(i)] = A[parent(i)], A[i]
        i = parent(i)

def insert(A, key):
    A.append(-float('inf'))
    heap_increase_key(A, key)

def max_heapify(A, i):
    H = len(A) - 1
    if H == 0:
        return
    l = left(i)
    r = right(i)

    child = {}
    child[i] = A[i] 
    if l <= H:
        child[l] = A[l]
    if r <= H:
        child[r] = A[r]
    largest = max(child.items(), key=lambda x:x[1])[0]

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

def heap_extract_max(A):
    H = len(A) - 1
    m = A[1]
    A[1] = A[H]
    del A[H]
    max_heapify(A, 1)
    return m

# main
A = [0]
while True:
    s = input().split()
    if s[0].startswith('i'):
        insert(A, int(s[1]))
    elif s[0].startswith('ex'):
        print(heap_extract_max(A))
    if s[0] == 'end':
        exit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
def left(i):
    return i * 2

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

def parent(i):
    return i // 2

def heap_increase_key(A, key):
    i = len(A) - 1
    A[i] = key
    while i > 1 and A[parent(i)] < A[i]:
        A[i], A[parent(i)] = A[parent(i)], A[i]
        i = parent(i)

def insert(A, key):
    A.append(-float('inf'))
    heap_increase_key(A, key)

def max_heapify(A, i):
    H = len(A) - 1
    if H == 0:
        return
    l = left(i)
    r = right(i)

    child = {}
    child[i] = A[i] 
    if l <= H:
        child[l] = A[l]
    if r <= H:
        child[r] = A[r]
    largest = max(child.items(), key=lambda x:x[1])[0]

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

def heap_extract_max(A):
    H = len(A) - 1
    m = A[1]
    A[1] = A[H]
    del A[H]
    max_heapify(A, 1)
    return m

# main
A = [0]
while True:
    s = sys.stdin.readline().split()
    if s[0].startswith('i'):
        insert(A, int(s[1]))
    elif s[0].startswith('ex'):
        print(heap_extract_max(A))
    if s[0] == 'end':
        exit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
import queue

# main
q = queue.PriorityQueue()
m = 2 * (10 ** 9)
while True:
    s = sys.stdin.readline().split()
    if s[0].startswith('i'):
        q.put(m - int(s[1]))
    elif s[0].startswith('ex'):
        print(m - q.get())
    if s[0] == 'end':
        exit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
import queue

# main
q = queue.PriorityQueue()
m = 2 * (10 ** 9)
S = sys.stdin.readlines()
for line in S:
    s = line.split()
    if s[0].startswith('i'):
        q.put(m - int(s[1]))
    elif s[0].startswith('ex'):
        print(m - q.get())
    if s[0] == 'end':
        exit()

Submission status: Time Limit Exceeded

Solution code:
def parent(n):
    return (n+1)/2-1

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

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

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    largest = i
    if l < len(A) and A[largest] < A[l]:
        largest = l
    if r < len(A) and A[largest] < A[r]:
        largest = r

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

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

def up_heap(A,i):
    p = parent(i)
    if p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        up_heap(A,p)

def extract_max(A):
    ret = A[0]
    A[0] = A[len(A)-1]
    del A[len(A)-1]
    max_heapify(A,0)
    return ret


heap = []
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        heap.append(n)
        up_heap(heap,len(heap)-1)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def parent(n):
    return (n+1)/2-1

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

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

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    largest = i
    if l < len(A) and A[largest] < A[l]:
        largest = l
    if r < len(A) and A[largest] < A[r]:
        largest = r

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

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

def up_heap(A,i):
    p = parent(i)
    if p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        up_heap(A,p)

def extract_max(A):
    ret = A[0]
    A[0] = A[len(A)-1]
    del A[len(A)-1]
    max_heapify(A,0)
    return ret


heap = []
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        heap.append(n)
        up_heap(heap,len(heap)-1)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def parent(n):
    return (n+1)/2-1

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

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

def max_heapify(A, i):
    global pt
    l = left(i)
    r = right(i)
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

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

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

def up_heap(A,i):
    p = parent(i)
    if p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        up_heap(A,p)

def extract_max(A):
    global pt
    ret = A[0]
    A[0] = A[pt]
    pt -= 1
    max_heapify(A,0)
    return ret


heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        pt += 1
        heap[pt] = n
        up_heap(heap,pt)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def parent(n):
    return (n+1)/2-1

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

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

def max_heapify(A, i):
    global pt
    l = left(i)
    r = right(i)
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

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

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

def up_heap(A,i):
    p = parent(i)
    while p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        i = p
        p = parent(i)

def extract_max(A):
    global pt
    ret = A[0]
    A[0] = A[pt]
    pt -= 1
    max_heapify(A,0)
    return ret


heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        pt += 1
        heap[pt] = n
        up_heap(heap,pt)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def parent(n):
    return (n+1)/2-1

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

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

def max_heapify(A, i):
    global pt
    l = left(i)
    r = right(i)
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

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

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

heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        pt += 1
        heap[pt] = n
        i = pt
        p = (i+1)/2-1
        while p >= 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = (i+1)/2-1
    elif c[1] == 'x':
        ret = heap[0]
        heap[0] = heap[pt]
        pt -= 1
        max_heapify(heap,0)
        print ret
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(A, i, pt):
    l = (i+1)*2-1
    r = (i+1)*2
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

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

heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        pt += 1
        heap[pt] = n
        i = pt
        p = (i+1)/2-1
        while p >= 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = (i+1)/2-1
    elif c[1] == 'x':
        ret = heap[0]
        heap[0] = heap[pt]
        pt -= 1
        max_heapify(heap,0,pt)
        print ret
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(A, i, pt):
    l = (i+1)*2-1
    r = (i+1)*2
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

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

heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        pt += 1
        heap[pt] = int(c[7:])
        i = pt
        p = (i+1)/2-1
        while p >= 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = (i+1)/2-1
    elif c[1] == 'x':
        print heap[0]
        heap[0] = heap[pt]
        pt -= 1
        max_heapify(heap,0,pt)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[largest] < A[l]:
        largest = l
    if r <= A[0] and A[largest] < A[r]:
        largest = r

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

heap = [0]*2000000
while True:
    c = raw_input()
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

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

heap = [0]*2000000
while True:
    c = raw_input()
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
class Pqueue:
    heap = []
    tail = -1

    def insert(self, k):
        self.heap.append(k)
        self.tail += 1
        self.bubble(self.tail)

    def bubble(self, i):
        if not i: return
        heap = self.heap
        pi = (i - 1) // 2
        if heap[i] > heap[pi]:
            heap[i], heap[pi] = heap[pi], heap[i]
            self.bubble(pi)

    def extract(self):
        heap = self.heap
        self.tail -= 1
        if self.tail < 0:
            return heap.pop()
        else:
            ret = heap[0]
            heap[0] = heap.pop()
            self.anchor(0)
            return ret

    def anchor(self, i):
        li, ri = i * 2 + 1, i * 2 + 2
        if li <= self.tail:
            heap = self.heap
            largest = li
            if ri <= self.tail and heap[ri] > heap[li]:
                largest = ri
            if heap[largest] > heap[i]:
                heap[i], heap[largest] = heap[largest], heap[i]
                self.anchor(largest)


pq = Pqueue()

while True:
    l = input()
    o = l[:2]
    if o == 'in':
        pq.insert(int(l.split()[1]))
    elif o == 'ex':
        print(pq.extract())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
heap = []
tail = -1


def insert(k):
    global heap, tail
    heap.append(k)
    tail += 1
    bubble(tail)


def bubble(i):
    global heap
    if not i: return
    pi = (i - 1) // 2
    if heap[i] > heap[pi]:
        heap[i], heap[pi] = heap[pi], heap[i]
        bubble(pi)


def extract():
    global heap, tail
    tail -= 1
    if tail < 0:
        return heap.pop()
    else:
        ret = heap[0]
        heap[0] = heap.pop()
        anchor(0)
        return ret


def anchor(i):
    global heap, tail
    li, ri = i * 2 + 1, i * 2 + 2
    if li <= tail:
        largest = li
        if ri <= tail and heap[ri] > heap[li]:
            largest = ri
        if heap[largest] > heap[i]:
            heap[i], heap[largest] = heap[largest], heap[i]
            anchor(largest)


while True:
    l = input()
    if l.startswith('i'):
        insert(int(l.split()[1]))
    elif l[1] == 'x':
        print(extract())
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
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 -1
        maxv = self.a[1]
        self.a[1] = self.a.pop()
        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.append(-1)
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [-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())