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: Wrong Answer

Solution code:
import sys


class priority_queue:
    def __init__(self, MAX_SIZE):
        self.array = [0]*MAX_SIZE
        self.size = 0

    def len(self):
        return self.size

    def empty(self):
        return self.size == 0

    def push(self, data):
        self.array[self.size] = data
        index = self.size
        while index != 0 and self.array[index] > self.array[(index-1)//2]:
            self.array[index], self.array[(index-1)//2] = \
                self.array[(index-1)//2], self.array[index]
            index = (index-1)//2
        self.size += 1

    def top(self):
        return self.array[0]

    def pop(self):
        self.array[0], self.array[self.size] = self.array[self.size], self.array[0]
        index = 0
        while 2 * index + 1 < self.size:
            if 2 * index + 2 < self.size:
                if self.array[2 * index + 2] > self.array[index] and \
                   self.array[2 * index + 2] >= self.array[2 * index + 1]:
                    self.array[2 * index + 2], self.array[index] =\
                        self.array[index], self.array[2 * index + 2]
                    index = 2 * index + 2
                elif self.array[2 * index + 1] > self.array[index] and \
                    self.array[2 * index + 1] >= self.array[index + 2]:
                    self.array[2 * index + 1], self.array[index] = \
                        self.array[index], self.array[2 * index + 1]
                    index = 2 * index + 1
                else:
                    break
            else:
                if self.array[2 * index + 1] > self.array[index]:
                    self.array[2 * index + 1], self.array[index] = \
                        self.array[index], self.array[2 * index + 1]
                    index = 2 * index + 1
                else:
                    break

if __name__ == '__main__':
    que = priority_queue(2000000)
    while True:
        s = sys.stdin.readline().split()
        if s[0] == "insert":
            que.push(int(s[1]))
        elif s[0] == "extract":
            sys.stdout.writelines("%d\n" % que.top())
            que.pop()
        else:
            break

Submission status: Wrong Answer

Solution code:
import sys


class priority_queue:
    def __init__(self, MAX_SIZE):
        self.array = [0]*MAX_SIZE
        self.size = 0

    def len(self):
        return self.size

    def empty(self):
        return self.size == 0

    def push(self, data):
        self.array[self.size] = data
        index = self.size
        while index != 0 and self.array[index] > self.array[(index-1)//2]:
            self.array[index], self.array[(index-1)//2] = \
                self.array[(index-1)//2], self.array[index]
            index = (index-1)//2
        self.size += 1

    def top(self):
        return self.array[0]

    def pop(self):
        self.size -= 1
        self.array[0], self.array[self.size] = self.array[self.size], self.array[0]
        index = 0
        while 2 * index + 1 < self.size:
            if 2 * index + 2 < self.size:
                if self.array[2 * index + 2] > self.array[index] and \
                   self.array[2 * index + 2] >= self.array[2 * index + 1]:
                    self.array[2 * index + 2], self.array[index] =\
                        self.array[index], self.array[2 * index + 2]
                    index = 2 * index + 2
                elif self.array[2 * index + 1] > self.array[index] and \
                    self.array[2 * index + 1] >= self.array[index + 2]:
                    self.array[2 * index + 1], self.array[index] = \
                        self.array[index], self.array[2 * index + 1]
                    index = 2 * index + 1
                else:
                    break
            else:
                if self.array[2 * index + 1] > self.array[index]:
                    self.array[2 * index + 1], self.array[index] = \
                        self.array[index], self.array[2 * index + 1]
                    index = 2 * index + 1
                else:
                    break

if __name__ == '__main__':
    que = priority_queue(2000000)
    while True:
        s = sys.stdin.readline().split()
        if s[0] == "insert":
            que.push(int(s[1]))
        elif s[0] == "extract":
            sys.stdout.writelines("%d\n" % que.top())
            que.pop()
        else:
            break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  9 13:21:18 2018
ALDS1-9c
@author: maezawa
"""
import math

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

def left(node):
    return 2*node

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

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

def build_max_heap(a):
    for i in list(range(1,h//2+1))[::-1]:
        max_heapify(a, i)
        #print(a)

def insert(key):
    global h
    h += 1
    a[h-1] = -3*10**9
    heap_increase_key(a, h, key)
        
def heap_increase_key(a, i, key):
    if key < a[i-1]:
        print('error')
        return False
    a[i-1] = key
    while i > 1 and a[parent(i)] < a[i-1]:
        a[i-1], a[parent(i)]  = a[parent(i)], a[i-1]
        i = parent(i)
    
def heap_extract(a):
    global h
    if h < 1:
        print('error')
    maxh = a[0]
    a[0] = a[h-1]
    h -= 1
    max_heapify(a, 1)
    return maxh
        
a = [0]*2000001
h = 0

while True:
    s = input()
    if s == 'end':
        break
    if s == 'extract':
        print(heap_extract(a))
        continue
    opcode, operand = s.split()
    data = int(operand)
    if opcode == 'insert':
        insert(data)

for i in range(h):
    print(' {}'.format(a[i]),end = '')
print()

Submission status: Wrong Answer

Solution code:
import sys

A = [0]*2000000
H = 0

def maxHeapify(i):
    global A
    l = i*2+1
    r = l+1
    # 左の子、自分、右の子で値が最大のノードを選ぶ
    largest = i
    if l < H and A[l] > A[i]:
        largest = l
    if r < H and A[r] > A[largest]:
        largest = r

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


while True:
    com = sys.stdin.readline()
    c = com[2]
    if c=='s': #com[0] == 'i': # insert
        _, 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 c=='t': # extract
        sys.stdout.write(str(A[0])+'\n')
        H-=1
        A[0] = A[H]
        largest = 0
        if 1 < H and A[1] > A[i]:        largest = 1
        if 2 < H and A[2] > A[largest]:  largest = 2
        if largest == 0:  continue
        A[0], A[largest] = A[largest], A[0]
        maxHeapify(largest) #  再帰的に呼び出し
    else: break

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
import heapq
q=[]
b=True
while b:
  n=input()
  if n=="end":
    b=False
    break
  elif n=="extract":
    i=heapq.heappop(q)
    print(-int(i))
  else:
    a,b=n.split()
    b=int(b)
    heapq.heappush(q,-b)

Submission status: Wrong Answer

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 i < l / 2:
        if queue[i] < queue[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
        elif queue[i] < queue[2 * i + 2]:
            queue = swap(queue, 2 * i + 2, i)
            i = 2 * i + 2
        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]))
        print queue

Submission status: Wrong Answer

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
        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: Wrong Answer

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, 1)
    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: Wrong Answer

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: Wrong Answer

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):
    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: Wrong Answer

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]
        p = 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: Wrong Answer

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,0)
    else:
        break

Submission status: Wrong Answer

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, a, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and a[l] > a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and a[r] > a[largest]:
            largest = r
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            self.maxHeapify(a, largest)

    def extract(self):
        if self.h < 1:
            return
        maxv = self.a[1]
        self.h -= 1
        self.a[1] = self.a[self.h]
        self.maxHeapify(self.a, 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, 2)
    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: Wrong Answer

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, a, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and a[l] > a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and a[r] > a[largest]:
            largest = r
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            self.maxHeapify(a, largest)

    def buildMaxHeap(self, a):
        for i in range(self.h//2, 0, -1):
            self.maxHeapify(a, i)
        return a

    def extract(self):
        if self.h < 1:
            return
        maxv = self.a[1]
        self.h -= 1
        self.a[1] = self.a[self.h]
        self.maxHeapify(self.a, 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, 1000000)
    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: Wrong Answer

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.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())

Submission status: Wrong Answer

Solution code:
import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, int(com[7:]))
    elif com[1] == "x":
        print(h.pop())

Submission status: Wrong Answer

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]:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]

    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:
            del self.keys[0]
        else:
            self.keys[0] = self.keys.pop()
        self.size -= 1
        if self.size > 1:
            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: Wrong Answer

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)
    if line[0] == "end":
        break

Submission status: Wrong Answer

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 = [-1]
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)
        maxHeapify(A, 1)
    elif line[0] == "end":
        break

Submission status: Wrong Answer

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)
        maxHeapify(A, 1)
    elif line[0] == "end":
        break

Submission status: Wrong Answer

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

def maxHeapify(A, i):
    n = A[0]
    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 = A[0]
    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]))
        A[0] += 1
        buildMaxHeap(A)
    elif line[0] == "extract":
        print A.pop(1)
        A[0] -= 1
        maxHeapify(A, 1)
    elif line[0] == "end":
        break

Submission status: Wrong Answer

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

def maxHeapify(A, i):
    n = A[0]
    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 = A[0]
    for i in range(n/2, 0, -1):
        maxHeapify(A, i)

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

Submission status: Wrong Answer

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()
	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: Wrong Answer

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 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]
    remove(S, 0)

def remove(S, i):
    l = left(i)
    r = right(i)

    if r >= len(S) and l < len(S) or r < len(S) and S[l] >= S[r]:
        S[i] = S[l]
        remove(S, l)
    elif r < len(S) and S[l] < S[r]:
        S[i] = S[r]
        remove(S, r)
    else:
        del S[i]

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: Wrong Answer

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 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]

    now = len(S) - 1
    if now % 2 == 0 and S[now] < S[now - 1]:
        S[now], S[now - 1] = S[now - 1], S[now]

    source = S[now]
    while True:
        p = parent(now)
        if p < 0:
            break
        target = S[p]
        S[p] = source
        source = target
        now = p
    S.pop()

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: Wrong Answer

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)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

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

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if l < len(S) and S[idx] < S[l]:
            S[idx], S[l] = S[l], S[idx]
            idx = l
        elif r < len(S) and S[idx] < S[r]:
            S[idx], S[r] = S[r], S[idx]
            idx = 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: Wrong Answer

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)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

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

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if l < len(S) and S[idx] < S[l] and r < len(S) and S[r] < S[l]:
            S[idx], S[l] = S[l], S[idx]
            idx = l
        elif r < len(S) and S[idx] < S[r] and S[l] < S[r]:
            S[idx], S[r] = S[r], S[idx]
            idx = 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)