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

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l <= last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r <= last and S[r] > S[largest]:
        largest = r

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

def extract():
    global S, last
    print S[0]
    S[0], S[last] = S[last], 0
    last -= 1
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
        last += 1
    else:
        extract()

Submission status: Wrong Answer

Solution code:
#coding:utf-8
#1_9_C
s = set()
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "insert":
        s.add(int(cmd[1]))
    else:
        print(max(s))
        s.remove(max(s))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
#1_9_C
d = dict()
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "insert":
        d[int(cmd[1])] = int(cmd[1])
    else:
        print(d.pop(max(d.values())))

Submission status: Wrong Answer

Solution code:
import sys
import os
import array

class priority_queue:
    def __init__(self, vals):
        self.vals=array.array('i', vals)

    def size(self):
        return len(self.vals)

#     def check(self, i):
#         assert(i >= 1)
#         assert(i <= self.size())

    def val_at(self, i):
#         self.check(i)
        return self.vals[i-1]

    def left_idx(self, i):
#         self.check(i)
        t = 2*i
        if t <= self.size():
            return t
        else:
            return None

    def right_idx(self, i):
#         self.check(i)
        t = 2*i + 1
        if t <= self.size():
            return t
        else:
            return None

    def parent_idx(self, i):
#         self.check(i)
        t = i//2
        if t > 0:
            return t
        else:
            return None

    def swap(self, i, j):
#         self.check(i); self.check(j)
        self.vals[i-1], self.vals[j-1] = self.vals[j-1], self.vals[i-1]

    def max_heapify(self, i):
#         self.check(i)
        l_idx = self.left_idx(i)
        r_idx = self.right_idx(i)
        swap_target = None

        if (l_idx is not None) and (self.val_at(l_idx) > self.val_at(i)):
            swap_target = l_idx
            # print('leftval, ival  ', self.val_at(l_idx), self.val_at(i), self.val_at(l_idx)>self.val_at(i))
            if r_idx is not None and self.val_at(r_idx) > self.val_at(l_idx):
                swap_target = r_idx
        elif r_idx is not None and self.val_at(r_idx) > self.val_at(i):
            swap_target = r_idx

        if swap_target is not None:
            # print('swap:', i, swap_target)
            self.swap(i, swap_target)
            self.max_heapify(swap_target)

    def build_max_heap(self):
        for i in reversed(range(1, self.size()//2+1)):
            # print('tgt: ', i)
            # print(self.vals)
            self.max_heapify(i)

    def insert(self, val):
        self.vals.append(val)
        heap_target = self.size()
        swap_candidate = heap_target//2
        while swap_candidate > 0:
            if self.vals[swap_candidate-1] < self.vals[heap_target-1]:
                self.vals[swap_candidate-1], self.vals[heap_target-1] = self.vals[heap_target-1], self.vals[swap_candidate-1]
                heap_target, swap_candidate = swap_candidate, swap_candidate//2
            else:
                break
                
#         while heap_target is not None:
#             self.max_heapify(heap_target)
#             heap_target = self.parent_idx(heap_target)


    def get_max(self):
        return self.vals(0)

    def extract_max(self):
        # self.swap(1, self.size())
        self.vals[0], self.vals[-1] = self.vals[-1], self.vals[0]
        ret = self.vals.pop()
        if self.size() > 0:
            self.max_heapify(1)
        return ret

    def show(self):
        return ''.join(map(lambda x: ' '+str(x), self.vals))


if __name__ == "__main__":
    # pq = priority_queue([])
    vals = [] 
    for line in sys.stdin:
        line = line.rstrip()
        cmd_val = line.split(' ')
        cmd, val = cmd_val + [None]*(2-len(cmd_val))        
#        print(cmd, val)
#        print(vals)
        if cmd == 'insert':
            # pq.insert(int(val))
            vals.append(int(val))
            heap_target = len(vals)
            swap_candidate = heap_target//2
            while swap_candidate > 0:
                if vals[swap_candidate-1] < vals[heap_target-1]:
                    vals[swap_candidate-1], vals[heap_target-1] = vals[heap_target-1], vals[swap_candidate-1]
                    heap_target, swap_candidate = swap_candidate, swap_candidate//2
                else:
                    break
        elif cmd == 'extract':
            # print(pq.extract_max())
            vals[0], vals[-1] = vals[-1], vals[0]
            ret = vals.pop()
            if len(vals) > 0:
                heapify_tgt = len(vals)//2
                while heapify_tgt > 0:
                    heap_target = len(vals)
                    swap_candidate = heap_target//2
                    while swap_candidate > 0:
                        if vals[swap_candidate-1] < vals[heap_target-1]:
                            vals[swap_candidate-1], vals[heap_target-1] = vals[heap_target-1], vals[swap_candidate-1]
                            heap_target, swap_candidate = swap_candidate, swap_candidate//2
                        else:
                            break
                    heapify_tgt = heapify_tgt//2
            print(ret)
        elif cmd == 'end':
            break

        # print(pq.show())

Submission status: Wrong Answer

Solution code:
import sys
import os
import array

class priority_queue:
    def __init__(self, vals):
        self.vals=array.array('i', vals)

    def size(self):
        return len(self.vals)

#     def check(self, i):
#         assert(i >= 1)
#         assert(i <= self.size())

    def val_at(self, i):
#         self.check(i)
        return self.vals[i-1]

    def left_idx(self, i):
#         self.check(i)
        t = 2*i
        if t <= self.size():
            return t
        else:
            return None

    def right_idx(self, i):
#         self.check(i)
        t = 2*i + 1
        if t <= self.size():
            return t
        else:
            return None

    def parent_idx(self, i):
#         self.check(i)
        t = i//2
        if t > 0:
            return t
        else:
            return None

    def swap(self, i, j):
#         self.check(i); self.check(j)
        self.vals[i-1], self.vals[j-1] = self.vals[j-1], self.vals[i-1]

    def max_heapify(self, i):
#         self.check(i)
        l_idx = self.left_idx(i)
        r_idx = self.right_idx(i)
        swap_target = None

        if (l_idx is not None) and (self.val_at(l_idx) > self.val_at(i)):
            swap_target = l_idx
            # print('leftval, ival  ', self.val_at(l_idx), self.val_at(i), self.val_at(l_idx)>self.val_at(i))
            if r_idx is not None and self.val_at(r_idx) > self.val_at(l_idx):
                swap_target = r_idx
        elif r_idx is not None and self.val_at(r_idx) > self.val_at(i):
            swap_target = r_idx

        if swap_target is not None:
            # print('swap:', i, swap_target)
            self.swap(i, swap_target)
            self.max_heapify(swap_target)

    def build_max_heap(self):
        for i in reversed(range(1, self.size()//2+1)):
            # print('tgt: ', i)
            # print(self.vals)
            self.max_heapify(i)

    def insert(self, val):
        self.vals.append(val)
        heap_target = self.size()
        swap_candidate = heap_target//2
        while swap_candidate > 0:
            if self.vals[swap_candidate-1] < self.vals[heap_target-1]:
                self.vals[swap_candidate-1], self.vals[heap_target-1] = self.vals[heap_target-1], self.vals[swap_candidate-1]
                heap_target, swap_candidate = swap_candidate, swap_candidate//2
            else:
                break
                
#         while heap_target is not None:
#             self.max_heapify(heap_target)
#             heap_target = self.parent_idx(heap_target)


    def get_max(self):
        return self.vals(0)

    def extract_max(self):
        # self.swap(1, self.size())
        self.vals[0], self.vals[-1] = self.vals[-1], self.vals[0]
        ret = self.vals.pop()
        if self.size() > 0:
            self.max_heapify(1)
        return ret

    def show(self):
        return ''.join(map(lambda x: ' '+str(x), self.vals))


if __name__ == "__main__":
    # pq = priority_queue([])
    vals = [] 
    for line in sys.stdin:
        line = line.rstrip()
        cmd_val = line.split(' ')
        cmd, val = cmd_val + [None]*(2-len(cmd_val))        
#         print(cmd, val)
#         print(vals)
        if cmd == 'insert':
            # pq.insert(int(val))
            vals.append(int(val))
            heap_target = len(vals)
            swap_candidate = heap_target//2
            while swap_candidate > 0:
                if vals[swap_candidate-1] < vals[heap_target-1]:
                    vals[swap_candidate-1], vals[heap_target-1] = vals[heap_target-1], vals[swap_candidate-1]
                    heap_target, swap_candidate = swap_candidate, swap_candidate//2
                else:
                    break
        elif cmd == 'extract':
            # print(pq.extract_max())
            vals[0], vals[-1] = vals[-1], vals[0]
            ret = vals.pop()
            size = len(vals)
            if size > 0:
                heapify_tgt = 1
                while heap_target <= size:
                    l_idx = heapify_tgt * 2
                    r_idx = l_idx + 1
                    if l_idx <= size and vals[l_idx-1] > vals[heapify_tgt-1]:
                        if r_idx <= size and vals[l_idx-1] > vals[r_idx-1]:
                            vals[r_idx-1], vals[heapify_tgt-1] = vals[heapify_tgt-1], vals[r_idx-1]
                            heapify_tgt = r_idx
                            continue
                        else:
                            vals[l_idx-1], vals[heapify_tgt-1] = vals[heapify_tgt-1], vals[l_idx-1]
                            heapify_tgt = l_idx
                            continue
                    elif r_idx <= size and vals[r_idx-1] > vals[heapify_tgt-1]:
                        vals[r_idx-1], vals[heapify_tgt-1] = vals[heapify_tgt-1], vals[r_idx-1]
                        heapify_tgt = r_idx
                        continue
                    else:
                        break
            print(ret)
        elif cmd == 'end':
            break

        # print(pq.show())

Submission status: Wrong Answer

Solution code:
from collections import deque

def get_item(L,i): return L[i] if len(L) > i else -1
def left (i): return i*2 + 1
def right(i): return (i+1)*2

def maxHeapify(A,i):
    l = left(i)
    r = right(i)
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(A,r) > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        maxHeapify(A, largest)


def insert(A,k):
    A.appendleft(k)
    maxHeapify(A,0)


if __name__=='__main__':
    hp = deque()
    while True:
        op = input().split() 
        if   op[0] == 'end': break
        if   op[0] == 'insert': insert(hp,int(op[1]))
        else: print(hp.popleft())

Submission status: Wrong Answer

Solution code:
from collections import deque

def get_item(L,i): return L[i] if len(L) > i else -1
def left (i): return i*2 + 1
def right(i): return (i+1)*2

def maxHeapify(A,i):
    l = left(i)
    r = right(i)
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(A,r) > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        maxHeapify(A, largest)


def insert(A,k):
    A.appendleft(k)
    maxHeapify(A,0)


def extract(A):
    max_item, A[0] = A[0], -1
    maxHeapify(A,0)
    A.remove(-1)
    return max_item


if __name__=='__main__':
    hp = deque()
    while True:
        op = input().split() 
        if   op[0] == 'end': break
        if   op[0] == 'insert': insert(hp,int(op[1]))
        else: print(extract(hp))

Submission status: Wrong Answer

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


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

for r in ret:
    print r

Submission status: Wrong Answer

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

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


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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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


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

if __name__ == "__main__":

    queue = PriorityQueue(2000000)

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

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

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

Submission status: Wrong Answer

Solution code:
def max_heapify(A, i):
  H = len(A) - 1
  l = i * 2
  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:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

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

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

Submission status: Wrong Answer

Solution code:
NIL = -1

class Heap:
    def __init__(self, L):
        self.H = len(L)
        self.heap = L
        self.heap.insert(0, 0)

    def parent(self, i):
        return i // 2

    def left(self, i):
        return 2 * i

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

    def insert(self, key):
        self.H += 1
        self.heap.append(NIL)
        self.heapIncreaseKey(self.H, key)

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

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

        return max

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

        if r <= self.H 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.maxHeapify(largest)

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

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

Submission status: Wrong Answer

Solution code:
NIL = -1

H = 0
heap = [0]
NIL = -1


def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


def insert(key):
    global H
    H += 1
    heap.append(NIL)
    heapIncreaseKey(H, key)


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


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

    return max


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

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

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

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

Submission status: Wrong Answer

Solution code:
NIL = -1

H = 0
heap = [0]
NIL = -1


def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


def insert(key):
    global H
    H += 1
    heap.append(NIL)
    heapIncreaseKey(H, key)


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


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

    return max


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

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

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

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

Submission status: Wrong Answer

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


def parent(i):
    return i // 2


def left(i):
    return 2 * i


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


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


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


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

    return max


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

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from math import floor

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    q = []
    H = 0
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q.append(int(cmd[1]))
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q[0]
            q[0] = q[-1]
            q.pop()
            H -= 1
            if H >= 2:
                maxHeapify(q,0,H)
        else:
            break

def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            v = A[p-1]
            A[p-1] = A[i-1]
            A[i-1] = v
            increase(A,p)
            
def maxHeapify(A,i,H):
    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:
        v = A[i-1]
        A[i-1] = A[largest-1]
        A[largest-1] = v
        maxHeapify(A,largest,H)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    q = range(int(2e+06))
    H = 0
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q[H]=int(cmd[1])
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q[0]
            q[0] = q[H]
            H -= 1
            if H >= 2:
                maxHeapify(q,1,H)
        else:
            break

def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            A[p-1], A[i-1] = A[i-1], A[p-1]
            increase(A,p)
            
def maxHeapify(A,i,H):
    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,H)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def extractMax(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        r = (i+1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
        else:
            lv = 0
        if r < H:
            rv = A[r]
        else:
            rv = 0
        if lv == 0 and rv == 0:
            break
        elif lv > rv:
            A[l] = A[i]
            A[i] = lv
            i = l
        else:
            A[r] = A[i]
            A[i] = rv
            i = r
    return x

def insert(A,n):
    A.append(n)
    i = len(A) - 1
    while i > 0:
        p = int((i + 1) / 2) - 1
#        print("p[{}]:{} i[{}]:{}".format(p, A[p], i, A[i]))
        if A[p] < A[i]: # ???????????§??????
            x = A[p]
            A[p] = A[i]
            A[i] = x
            i = p
        else:
            break

def main():

    """ ????????? """
    end = False
    S = []
    
    while end != True:
        cmd = input()
#        print("cmd:{} S:{}".format(cmd,S))
        if cmd == "extract":
            a = extractMax(S)
            print(a)
            
        elif cmd == "end":
            end = True

        elif cmd[0] == "i":
            insert(S,int(cmd[7:]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from math import floor
sys.setrecursionlimit(100000)

INF = float("inf")
inp = [0]
A = [None]

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



def insert(A, key):
    
    A.append(-INF)
    heap_increase_key(A, key)


def heap_increase_key(A, key):
    i = len(A) - 1
    A[-1] = key
    
    if key < A[i]:
        pass

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

def heap_extract_max(A):
    
    max_, A[1] = A[1] , A[-1]
    A = A[:-1]
    max_heapify(A, 1)
    
    return max_


while inp[0] != "end":
    inp = [n for n in input().split()]
    if inp[0] == "insert":
        insert(A, int(inp[1]))
    elif inp[0] == "extract":
        max_ = heap_extract_max(A)
        print(max_)

Submission status: Wrong Answer

Solution code:
def insert(S, k):
    S.append(k)
    buildMaxHeap(S)

def extractMax(S):
    ret = S[0]
    S[:] = S[1:]
    return ret

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

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

S = []
i = input()
while i != 'end':    
    if i == 'extract':
        print(extractMax(S))
    else:
        op, k = i.split()
        insert(S, int(k))
    i = input()