Problem:


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

Priority Queue

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

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

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

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

Input

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

The input ends with "end" operation.

Output

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

Constraints

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

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

Sample Input 1

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

Sample Output 1

8
10
11
2



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


Sample output:
8
10
11
2

Submission status: Time Limit Exceeded

Solution code:
import sys

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)
    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]
    S[0] = S[-1]
    S.pop()

    now = 0
    while True:
        l, r = left(now), right(now)
        if r < len(S):
            if S[now] < S[l] and S[r] <= S[l]:
                S[now], S[l] = S[l], S[now]
                now = l
            elif S[now] < S[r] and S[l] <= S[r]:
                S[now], S[r] = S[r], S[now]
                now = r
            else:
                break
        elif l < len(S):
            if S[now] < S[l]:
                S[now], S[l] = S[l], S[now]
                now = l
            else:
                break
        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: Time Limit Exceeded

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 r < len(S):
            if S[idx] < S[l] and S[r] <= S[l]:
                S[idx], S[l] = S[l], S[idx]
                idx = l
            elif S[idx] < S[r] and S[l] <= S[r]:
                S[idx], S[r] = S[r], S[idx]
                idx = r
            else:
                break
        elif l < len(S):
            if S[idx] < S[l]:
                S[idx], S[l] = S[l], S[idx]
                idx = l
            else:
                break
        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: Time Limit Exceeded

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
    #print S

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] or r >= len(S)):
            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
    #print S

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

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
    #print S

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] or r >= len(S)):
            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
    #print S

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

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 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 extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()
    maxHeapify(S, 0)

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

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

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
#1_9_C
import queue

q = queue.PriorityQueue()
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "insert":
        q.put(-int(cmd[1]))
    else:
        print(-q.get())

Submission status: Time Limit Exceeded

Solution code:
import sys

class priority_queue:
    def __init__(self, vals):
        self.vals=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()
        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())
        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([])
    for line in sys.stdin:
        line = line.rstrip()
        # print(line)
        cmd_val = line.split(' ')
        cmd, val = cmd_val + [None]*(2-len(cmd_val))
        if cmd == 'end':
            break
        elif cmd == 'extract':
            print(pq.extract_max())
        elif cmd == 'insert':
            pq.insert(int(val))
        # print(pq.show())

Submission status: Time Limit Exceeded

Solution code:
import sys

class priority_queue:
    def __init__(self, vals):
        self.vals=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())
        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([])
    for line in sys.stdin:
        line = line.rstrip()
        cmd_val = line.split(' ')
        cmd, val = cmd_val + [None]*(2-len(cmd_val))        

        if cmd == 'insert':
            pq.insert(int(val))
        elif cmd == 'extract':
            print(pq.extract_max())
        elif cmd == 'end':
            break

        # print(pq.show())

Submission status: Time Limit Exceeded

Solution code:
import sys
 
class priority_queue:
    def __init__(self, vals):
        self.vals=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())
        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([])
    for line in sys.stdin:
        line = line.rstrip()
        cmd_val = line.split(' ')
        cmd, val = cmd_val + [None]*(2-len(cmd_val))        
 
        if cmd == 'insert':
            pq.insert(int(val))
        elif cmd == 'extract':
            print pq.extract_max()
        elif cmd == 'end':
            break
 
        # print(pq.show())

Submission status: Time Limit Exceeded

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
        print("->", vals)        
#         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("LINE: ", 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
#             print("->", vals)


        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
                #print("?", heapify_tgt, size)
                while heapify_tgt <= 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
                            #print('    a')
                            continue
                        else:
                            vals[l_idx-1], vals[heapify_tgt-1] = vals[heapify_tgt-1], vals[l_idx-1]
                            heapify_tgt = l_idx
                            #print('    b')
                            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
                        #print('    c')
                        continue
                    else:
                        #print('    d')
                        break
            #print("e>", vals)
            print(ret)
        elif cmd == 'end':
            break

        # print(pq.show())

Submission status: Time Limit Exceeded

Solution code:
def get_item(L,i): return L[i] if len(L) > i else -2
def left(i): return i*2 + 1
def right(i): return (i+1)*2
def parent(i): return i//2 if i%2 == 1 else i//2 - 1

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 maxHeapInsert(A,i):
    if i==0: return
    p = parent(i)
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        maxHeapInsert(A,p)


def insert(A,k):
    A.append(k)
    maxHeapInsert(A,len(A)-1)


def extract(A):
    max_item, A[0] = A[0], -1
    maxHeapify(A,0)
    for i in range(A.index(-1),len(A)-1):
        A[i], A[i+1] = A[i+1], A[i]
        maxHeapInsert(A,i)
    A.pop()
    return max_item


if __name__=='__main__':
    hp = []
    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: Time Limit Exceeded

Solution code:
def get_item(L,i): return L[i] if len(L) > i else -2
def left(i): return i*2 + 1
def right(i): return (i+1)*2
def parent(i): return i//2 if i%2 == 1 else i//2 - 1

def dw_heap(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] 
        dw_heap(A, largest)


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


def insert(A,k):
    A.append(k)
    up_heap(A,len(A)-1)


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


if __name__=='__main__':
    hp = []
    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: Time Limit Exceeded

Solution code:
def get_item(L,i): return L[i] if len(L) > i else -2

def dw_heap(A,i):
    l = i*2 + 1
    r = (i+1)*2
    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] 
        dw_heap(A, largest)


def up_heap(A,i):
    if i==0: return
    p = i//2 if i%2 == 1 else i//2 - 1
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def insert(A,k):
    A.append(k)
    up_heap(A,len(A)-1)


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


if __name__=='__main__':
    hp = []
    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: Time Limit Exceeded

Solution code:
def dw_heap(A,i):
    alen = len(A)
    l = i*2 + 1
    r = (i+1)*2
    largest = i
    if l < alen and A[l] > A[largest]: largest = l
    if r < alen and A[r] > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        dw_heap(A, largest)


def up_heap(A,i):
    if i==0: return
    p = i//2 if i%2 == 1 else i//2 - 1
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def insert(A,k):
    A.append(k)
    up_heap(A,len(A)-1)


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


if __name__=='__main__':
    hp = []
    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: Time Limit Exceeded

Solution code:
def dw_heap(A,i,length):
    l = i*2
    r = i*2 + 1
    largest = i
    if l < length and A[l] > A[largest]: largest = l
    if r < length and A[r] > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        dw_heap(A, largest, length)


def up_heap(A,i):
    if i==1: return
    p = i//2
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def extract(A,last):
    max_item = A[1]
    A[1],A[last] = A[last],A[1]
    dw_heap(A,1,last)
    return max_item


def build_heap(A,length):
    for i in range(length//2,0,-1): dw_heap(A,i,length)


if __name__=='__main__':
    hp = [None]*2*10**6
    i = 1
    while True:
        op = input().split() 
        if   op[0] != 'insert': break
        hp[i] = int(op[1])
        i += 1
    if op[0] != 'end': build_heap(hp,i)
    while True:
        if   op[0] == 'end': break
        if   op[0] == 'insert':
            hp[i] = int(op[1])
            up_heap(hp,i)
            i += 1
        else:
            print(extract(hp,i-1))
            i -= 1
        op = input().split()

Submission status: Time Limit Exceeded

Solution code:
def dw_heap(A,i,length):
    l = i*2
    r = i*2 + 1
    largest = i
    if l < length and A[l] > A[largest]: largest = l
    if r < length and A[r] > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        dw_heap(A, largest, length)


def up_heap(A,i):
    if i==1: return
    p = i//2
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def extract(A,last):
    max_item = A[1]
    A[1],A[last] = A[last],A[1]
    dw_heap(A,1,last)
    return max_item


def build_heap(A,length):
    for i in range(length//2,0,-1): dw_heap(A,i,length)


if __name__=='__main__':
    hp = [None]*(2*10**6)
    i = 1
    j = -1 
    while True:
        op = input() 
        if   op[0] != 'i': break
        hp[i] = int(op[7:])
        i += 1
    if op[2] != 'd': build_heap(hp,i)
    while True:
        if   op[2] == 'd': break
        if   op[0] == 'i':
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        else:
            hp[j] = extract(hp,i-1)
            i -= 1
            j -= 1
        op = input() 
    print(*hp[:j:-1],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def dw_heap(A,i,length):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if l < length and A[l] > A[largest]: largest = l
        if r < length and A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest


def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2


def extract(A,last):
    max_item = A[1]
    A[1],A[last] = A[last],A[1]
    dw_heap(A,1,last)
    return max_item


def build_heap(A,length):
    for i in range(length//2,0,-1): dw_heap(A,i,length)


if __name__=='__main__':
    hp = [None]*(2*10**6)
    hp[0] = 2*10**9 + 1
    i = 1
    j = -1 
    while True:
        op = input() 
        if   op[0] != 'i': break
        hp[i] = int(op[7:])
        i += 1
    if op[2] != 'd': build_heap(hp,i)
    while True:
        if   op[2] == 'd': break
        if   op[0] == 'i':
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        else:
            hp[j] = extract(hp,i-1)
            i -= 1
            j -= 1
        op = input() 
    print(*hp[:j:-1],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def dw_heap(A,i,length):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if l < length and A[l] > A[largest]: largest = l
        if r < length and A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest


def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2


def build_heap(A,length):
    for i in range(length//2,0,-1): dw_heap(A,i,length)


if __name__=='__main__':
    hp = [None]*(2*10**6)
    hp[0] = 2*10**9 + 1
    i = 1
    j = -1 
    while True:
        op = input() 
        if   op[0] != 'i': break
        hp[i] = int(op[7:])
        i += 1
    if op[2] != 'd': build_heap(hp,i)
    while True:
        if   op[2] == 'd': break
        if   op[0] == 'i':
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        else:# extract
            hp[j] = hp[1]
            hp[1],hp[i-1] = hp[i-1],hp[1]
            dw_heap(hp,1,i-1)
            i -= 1
            j -= 1
        op = input() 
    print(*hp[:j:-1],sep='\n')