This question is designed to help you get a better understanding of basic heap operations.  

There are $3$ types of query:

"$1$ $\boldsymbol{\nu}$"  - Add an element $\boldsymbol{\nu}$ to the heap.  
"$2$ $\boldsymbol{\nu}$"  - Delete the element $\boldsymbol{\nu}$ from the heap.  
"$3$" - Print the minimum of all the elements in the heap.

NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.

Input Format

The first line contains the number of queries, $Q$. 

Each of the next $Q$ lines contains one of the $3$ types of query.   

Constraints 

$1\leq Q\leq10^5$ 

$-10^9\leq v\leq10^9$

Output Format

For each query of type $3$, print the minimum value on a single line.  

Sample Input
STDIN       Function
-----       --------
5           Q = 5
1 4         insert 4
1 9         insert 9
3           print minimum
2 4         delete 4
3           print minimum

Sample Output
4  
9 

Explanation

After the first $2$ queries, the heap contains {$4,9$}. Printing the minimum gives $\begin{array}{c}4\end{array}$ as the output. Then, the $4^{th}$ query deletes $\begin{array}{c}4\end{array}$ from the heap, and the $5^{th}$ query gives $\mbox{9}$ as the output.

Source: hackerrank | Difficulty: EASY
Tags: Data structures


Solutions:
import math
import sys

class Tree(object):

	def left(self, index):
		return 2 * index + 1

	def get_if_present(self, idx):
		if idx < len(self.list):
			return self.list[idx]
		else:
			return None

	def lval(self, index):
		return self.get_if_present(self.left(index))

	def rval(self, index):
		return self.get_if_present(self.right(index))

	def right(self, index):
		return self.left(index) + 1

	def parent(self, index):
		return math.floor((index - 1) / 2)

	def insert(self, val):
		self.list.append(val)
		return len(self.list) - 1

	def find(self, val):
		return self.list.index(val)

	def __init__(self):
		self.list = []

def insert(tree, value):
	idx = tree.insert(value)
	while tree.list[tree.parent(idx)] > value and idx > 0:
		tree.list[idx] = tree.list[tree.parent(idx)]
		tree.list[tree.parent(idx)] = value
		idx = tree.parent(idx)

def remove(tree, value):
	idx = tree.find(value)

	def match(tv, lval, rval):
		if lval and tv > lval:
			return True
		if rval and tv > rval:
			return True
		return False
	if idx == len(tree.list) - 1:
		tree.list.pop()
		return
	tree.list[idx] = tree.list.pop()
	while match(tree.list[idx], tree.lval(idx), tree.rval(idx)):
		left = tree.left(idx)
		right = tree.right(idx)
		rv = tree.rval(idx)
		lv = tree.lval(idx)
		ov = tree.list[idx]
		if rv and ov > rv and (lv is None or lv > rv):
			tree.list[idx] = rv
			tree.list[right] = ov
			idx = right
		elif lv and ov > lv and (rv is None or rv > lv):
			tree.list[idx] = lv
			tree.list[left] = ov
			idx = left

def print_min(heap):
	print(heap.list[0])
heap = Tree()
skip = True
for line in sys.stdin:
	if skip:
		skip = False
		continue
	line = line.rstrip()
	commands = line.split(' ')
	if commands[0] == '1':
		insert(heap, int(commands[1]))
	if commands[0] == '2':
		remove(heap, int(commands[1]))
	if commands[0] == '3':
		print_min(heap)


heap = []
try:
	b = input()
	mini = None
	while True:
		x = input().split(' ')
		if x[0] == '1':
			heap.append(int(x[1]))
			if mini == None or int(x[1]) < mini:
				mini = int(x[1])
		elif x[0] == '2':
			heap.remove(int(x[1]))
			if int(x[1]) == mini and heap != []:
				mini = min(heap)
			elif heap == []:
				mini = None
		elif x[0] == '3':
			print(mini)
except:
	pass