None def swap def sift_up while if break else swap def add append sift

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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