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: Runtime Error

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:2
            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: Runtime Error

Solution code:
a = []
while(True):
 x = input().split()
 if x[0] == "end":
  quit()
 elif x[0] == "insert":
  a.append(x[1])
  a.sort(reversed = True)
 else:
  print(a[0])
  del(a[0])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
INF = -10**10
queue = [-1]


def insert(queue, key):
    h = len(queue) - 1
    queue.append(INF)
    heap_increase_key(queue, h + 1, key)


def heap_increase_key(queue, i, key):
    if key < queue[i]:
        raise ValueError('The new key is smaller than the present key')
    queue[i] = key
    while i > 1 and queue[i // 2] < queue[i]:
        queue[i], queue[i // 2] = queue[i // 2], queue[i]
        i = i // 2


def extract_max(queue):
    h = len(queue) - 1
    if h < 1:
        raise TypeError('Heap underflowed')
    max = queue[1]
    queue[1] = queue.pop()
    max_heapify(queue, 1)

    return max


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

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


if __name__ == '__main__':
    import sys
    ords = [line.strip().split() for line in sys.stdin]

    for ord in ords:
        if len(ord) > 1:
            ord, key = ord

        if ord[0] == 'i':
            insert(queue, key)
        elif len(ord) == 7:
            extract_max(queue)
        else:
            break

Submission status: Runtime Error

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

MININT = -1 - maxint


def max_heapify(a, i, heap_size):
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest, heap_size)


def max_heap_insert(a, key, heap_size):
    heap_size[0] += 1
    a[heap_size[0]] = MININT
    heap_increase_key(a, key, heap_size[0])


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


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


heap = array('i', [MININT] * 2000001)
heap_size = [1]
for cmd in stdin:
    if cmd[0] == 'i':
        key = int(cmd[7:])
        #assert 0 <= key <= 2000000000
        max_heap_insert(heap, key, heap_size)
    elif cmd[1] == 'x':
        print(heap_extract_max(heap, heap_size))
    elif cmd[1] == 'n':
        break