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:
# -*- coding: utf-8 -*-

def parent(i):
    return i // 2


def left(i):
    return 2 * i


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

class MaxHeap(list):
    def __init__(self, H=0):
        list.__init__(self)
        self.H = H
        self[:] = [None] * (H+1)

    def insert(self, key):
        self.H += 1
        self.append(-float("inf"))
        self.heapIncreaseKey(self.H, key)

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

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = A[self.H]
        self.H -= 1
        self.maxHeapify(1)

        return maximum

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

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

        


if __name__ == '__main__':

    A = MaxHeap()
    c = [None, None]
    while c[0] != "end":
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            pass

Submission status: Wrong Answer

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

def parent(i):
    return i // 2


def left(i):
    return 2 * i


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

class MaxHeap(list):
    def __init__(self, H=0):
        list.__init__(self)
        self.H = H
        self[:] = [None] * (H+1)

    def insert(self, key):
        self.H += 1
        self.append(-float("inf"))
        self.heapIncreaseKey(self.H, key)

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

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = A[self.H]
        self.H -= 1
        self.maxHeapify(1)

        return maximum

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

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

        


if __name__ == '__main__':

    A = MaxHeap()
    while True:
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            break

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]
for a in iter(input,'end'):
 if a[0]=='i':
  H+=1;A+=[int(a[7:])];k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 else:
  print(A[1])
  if H-1:A[1]=A.pop()
  H-=1;h(1)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
H,O=[],''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=f'{-heappop(H)}\n'
print(O[-1])

Submission status: Wrong Answer

Solution code:
import sys


class QueueEmptyError(Exception):
    pass


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

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

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

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

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

        return node


def run():
    q = PriorityQueue()

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


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

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

    def max_heapify(self, i):
        l = (i+1)*2-1
        r = (i+1)*2
        largest = i
        if l < self.num_node and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i
        if r < self.num_node and self.heap[r] > self.heap[largest]:
            largest = r

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

    def insert(self, k):
        self.heap.append(k)
        i = int((self.num_node-1)/2)
        self.num_node += 1
        while i != 0:
            self.max_heapify(i)
            i = int(i/2)
        self.max_heapify(i)

    def extract_max(self):
        if self.num_node == 1:
            self.num_node = 0
            return self.heap.pop()
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.num_node -= 1
        self.max_heapify(0)
        return max_val

pq = PriorityQueue()
while True:
    op = input()
    if op == 'end': break
    if op == 'extract':
        print(pq.extract_max())
    else:
        ope, num = op.split(' ')
        num = int(num)
        pq.insert(num)

Submission status: Wrong Answer

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

    def max_heapify(self, i):
        l = (i+1)*2-1
        r = (i+1)*2
        largest = i
        if l < self.num_node and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i
        if r < self.num_node and self.heap[r] > self.heap[largest]:
            largest = r

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

    def exchange(self, i):
        l = (i+1)*2-1
        r = (i+1)*2
        largest = i
        if l < self.num_node and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i
        if r < self.num_node and self.heap[r] > self.heap[largest]:
            largest = r

        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]

    def insert(self, k):
        self.heap.append(k)
        i = int((self.num_node-1)/2)
        self.num_node += 1
        while i != 0:
            self.exchange(i)
            i = int(i/2)
        self.max_heapify(i)

    def extract_max(self):
        if self.num_node == 1:
            self.num_node = 0
            return self.heap.pop()
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.num_node -= 1
        self.max_heapify(0)
        return max_val

pq = PriorityQueue()
while True:
    op = input()
    if op == 'end': break
    if op == 'extract':
        print(pq.extract_max())
    else:
        ope, num = op.split(' ')
        num = int(num)
        pq.insert(num)

Submission status: Wrong Answer

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

    def max_heapify(self, i):
        l = (i+1)*2-1
        r = (i+1)*2
        largest = i
        if l < self.num_node and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i
        if r < self.num_node and self.heap[r] > self.heap[largest]:
            largest = r

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

    def exchange(self, i):
        l = (i+1)*2-1
        r = (i+1)*2
        largest = i
        if l < self.num_node and self.heap[l] > self.heap[i]:
            largest = l
        else:
            largest = i
        if r < self.num_node and self.heap[r] > self.heap[largest]:
            largest = r

        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]

    def insert(self, k):
        self.heap.append(k)
        i = int((self.num_node-1)/2)
        self.num_node += 1
        while i != 0:
            self.exchange(i)
            i = int(i/2)
        self.exchange(i)

    def extract_max(self):
        if self.num_node == 1:
            self.num_node = 0
            return self.heap.pop()
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.num_node -= 1
        self.max_heapify(0)
        return max_val

pq = PriorityQueue()
while True:
    op = input()
    if op == 'end': break
    if op == 'extract':
        print(pq.extract_max())
    else:
        ope, num = op.split(' ')
        num = int(num)
        pq.insert(num)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

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

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

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

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

pq = PriorityQueue()

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

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

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

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

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

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

pq = PriorityQueue()

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

Submission status: Wrong Answer

Solution code:
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)

def insert_heap(i, node_list):
    node_list.append(i)
    k = len(node_list) - 1
    while(node_list[k] > node_list[k//2]):
        node_list[k], node_list[k//2] = node_list[k//2], node_list[k]
        k = k//2


def extract_heap(node_list):
    print(node_list[0])
    pop = node_list.pop()
    n = len(node_list)
    if n != 0:
        node_list[0] = pop
        maxHeapify(0, node_list)

import sys
input_list = sys.stdin.readlines()
node_list = []
for line in input_list:
    line = line.split()
    if line[0] == 'end':
        break
    elif line[0] == 'extract':
        extract_heap(node_list)
    else:
        insert_heap(int(line[1]), node_list)

Submission status: Wrong Answer

Solution code:
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)

def insert_heap(i, node_list):
    node_list.append(i)
    k = len(node_list) - 1
    parent_i = (k+1)//2 -1
    while(node_list[k] > node_list[parent_i] and k>0):
        node_list[k], node_list[parent_i] = node_list[parent_i], node_list[k]
        k = parent_i


def extract_heap(node_list):
    print(node_list[0])
    pop = node_list.pop()
    n = len(node_list)
    if n != 0:
        node_list[0] = pop
        maxHeapify(0, node_list)

import sys
input_list = sys.stdin.readlines()
node_list = []
for line in input_list:
    line = line.split()
    if line[0] == 'end':
        break
    elif line[0] == 'extract':
        extract_heap(node_list)
    else:
        insert_heap(int(line[1]), node_list)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
A = []
H = 0
def maxHeapify(A,i):
    if len(A) <= 1:
        return
    l = 2 * i
    r = 2 * i + 1
    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]
        maxHeapify(A,largest)

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

def Insert(key):
    global H
    H += 1
    A.append(-1111)
    heapIncreaseKey(A,H,key)

def heapIncreaseKey(A,i,key):
    if key < A[i-1]:
        return
    A[i-1] = key
    while i > 1 and A[i//2 - 1] < A[i-1]:
        A[i-1], A[i//2 -1] = A[i//2 - 1], A[i-1]
        i //= 2

def heapExtractMax(A):
    global H
    if H < 1:
        return
    maxv = A[0]
    A[0] = A[H-1]
    H -= 1
    A.pop()
    maxHeapify(A,0)
    return maxv

while True:
    data = list(input().split())
    if data[0] == "insert":
        Insert(int(data[1]))
    elif data[0]  == "extract":
        maxv = heapExtractMax(A)
        print(maxv)
    else:
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def max_heapify(a, i):
    heap_size = len(a)
    L = 2*i - 1
    R = 2*i
    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 max_heap_insert(a, key):
    a.append(-1 - maxint)
    heap_increase_key(a, key, len(a)-1)


def heap_increase_key(a, key, i):
    if key < a[i]:
        raise ValueError('new key less current key')
    a[i] = key
    while i > 0 and a[i//2 -1] < a[i]:
        a[i], a[i//2 -1] = a[i//2 -1], a[i]
        i = i//2 -1


def heap_extract_max(a):
    heap_size = len(a)-1
    if heap_size < 0:
        raise ValueError('heap under flow')
    max = a[0]
    a[0] = a[heap_size]
    max_heapify(a, 0)
    return max


heap = []
for cmd in stdin:
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert 0 <= key <= 2000000000
        max_heap_insert(heap, key)
    elif cmd.startswith('ex'):
        print(heap_extract_max(heap))
    elif cmd.startswith('en'):
        break

Submission status: Time Limit Exceeded

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

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[2 * 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)
    for s in sys.stdin.readlines():
        if s[0] == 'i':
            que.push(int(s[7:]))
        elif s[1] == 'x':
            sys.stdout.writelines("%d\n" % que.top())
            que.pop()
        else:
            break

Submission status: Time Limit Exceeded

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[2 * 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)
    for s in sys.stdin.readlines():
        if s[0] == 'i':
            que.push(int(s[7:]))
        elif s[1] == 'x':
            print(que.top())
            que.pop()
        else:
            break

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
A = []
inf = 100000000000

def maxHeapify(A, i):
    l = 2 * i
    r = 2 * i  + 1
    H = len(A)

    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]                                                                                                                                    
        maxHeapify(A, largest)
        
def Insert(key):
    A.append(key)
    i = len(A)
    while i > 1 and A[i // 2 - 1] < A[i-1] :
        A[i-1], A[i // 2 - 1] = A[i // 2 - 1], A[i - 1]
        i = i// 2

def heapExtractMax(A):
    if len(A) == 0:
        return
    maxv = A[0]
    A[0] = A[-1]
    maxHeapify(A, 1)
    A.pop()

    return maxv

while True:
    data = list(input().split())
    if data[0] == "end":
        break
    elif data[0] == "insert":
        Insert(int(data[1]))
    else:
        maxv = heapExtractMax(A)
        print(maxv)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
A = []
inf = 100000000000

def maxHeapify(A, i):
    l = 2 * i
    r = 2 * i  + 1
    H = len(A)

    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]                                                                                                                                    
        maxHeapify(A, largest)
        
def Insert(key):
    A.append(key)
    i = len(A)
    while i > 1 and A[i // 2 - 1] < A[i-1] :
        A[i-1], A[i // 2 - 1] = A[i // 2 - 1], A[i - 1]
        i = i// 2

def heapExtractMax(A):
    if len(A) == 0:
        return
    maxv = A[0]
    A[0] = A[-1]
    maxHeapify(A, 1)
    A.pop()

    return maxv

while True:
    data = list(input().split())
    if data[0] == "insert":
        Insert(int(data[1]))
    elif data[0] == "extract":
        maxv = heapExtractMax(A)
        print(maxv)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
def maxHeapify(A, i):
    l = 2 * i
    r = 2 * i  + 1
    H = len(A)

    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]                                                                                                                                    
        maxHeapify(A, largest)
        
def Insert(key):
    A.append(key)
    i = len(A)
    while i > 1 and A[i // 2 - 1] < A[i-1] :
        A[i-1], A[i // 2 - 1] = A[i // 2 - 1], A[i - 1]
        i = i// 2

def heapExtractMax(A):
    if len(A) == 0:
        return
    maxv = A[0]
    A[0] = A[-1]
    maxHeapify(A, 1)
    A.pop()

    return maxv

A = []
while True:
    data = list(input().split())
    if data[0] == "insert":
        Insert(int(data[1]))
    elif data[0] == "extract":
        maxv = heapExtractMax(A)
        print(maxv)
    else:
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

count = {}
maxval = 0
while True:
    com = sys.stdin.readline()
    if com[2] == 'd':
        break
    if com[0] == 'i':
        _, arg = com.split()
        k = int(arg)
        if maxval<k: maxval = k
        count[k] = count.get(k, 0) + 1
    elif com[0] == 'e':
        print(maxval)
        count[maxval]-=1
        if count[maxval]==0:
            count.pop(maxval)
            if len(count)>0:  maxval = max(count.keys())

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