1class heap:
2 def __init__(self):
3 self.t=[]
4
5 def push(self, x):
6 t=self.t
7 t.append(x)
8 k=len(t)-1
9 while k:
10 m=(k-1)//2
11 if t[k]<t[m]:
12 t[k], t[m]=t[m], t[k]
13 k=m
14 else:
15 break
16 def pop(self):
17 t=self.t
18 if not t:
19 raise IndexError("pop from empty heap")
20 if len(t)==1:
21 return t.pop()
22 root=t[0]
23 t[0]=t.pop()
24 k=0
25
26 while True:
27 L=[i for i in [2*k+1, 2*k+2] if i<len(t)]
28 if not L:
29 break
30 mini=min(t[i] for i in L)
31 if t[k]<mini:
32 break
33 for i in L:
34 if t[i]==mini:
35 t[i],t[k]=t[k], t[i]
36 k=i
37 break
38
39 return root
40
41
42from random import randrange
43
44
45n=6
46h=heap()
47
48
49for _ in range(n):
50 x=randrange(10,100)
51 h.push(x)
52 print(x, h.t)
53
54print()
55
56for _ in range(n):
57 print(h.pop())
58
1from heapq import heappush, heappop
2from random import randrange
3
4n=6
5L=[]
6for _ in range(n):
7 x=randrange(10,100)
8 heappush(L, x)
9 print(x, L)
10
11print()
12
13for _ in range(n):
14 print(heappop(L))
15