H = [None]
def swap(a, b):
H[a], H[b] = H[b], H[a]
def sift_up(v):
while v != 1:
if H[v // 2] > H[v]:
break
else:
swap(v // 2, v)
v = v // 2
def add(x):
H.append(x)
sift_up(len(H) - 1)
def sift_down(v):
while 2 * v < len(H):
ind = 2 * v
if 2 * v + 1 < len(H) and H[2 * v + 1] > H[2 * v]:
ind = 2 * v + 1
if H[ind] < H[v]:
break
swap(v, ind)
v = ind
def extract_min():
swap(1, len(H) - 1)
ret = H.pop()
sift_down(1)
return ret