opérations des file de priorités en python
class heap:
def __init__(self):
self.t=[]
def push(self, x):
t=self.t
t.append(x)
k=len(t)-1
while k:
m=(k-1)//2
if t[k]<t[m]:
t[k], t[m]=t[m], t[k]
k=m
else:
break
def pop(self):
t=self.t
if not t:
raise IndexError("pop from empty heap")
if len(t)==1:
return t.pop()
root=t[0]
t[0]=t.pop()
k=0
while True:
L=[i for i in [2*k+1, 2*k+2] if i<len(t)]
if not L:
break
mini=min(t[i] for i in L)
if t[k]<mini:
break
for i in L:
if t[i]==mini:
t[i],t[k]=t[k], t[i]
k=i
break
return root
from random import randrange
n=6
h=heap()
for _ in range(n):
x=randrange(10,100)
h.push(x)
print(x, h.t)
print()
for _ in range(n):
print(h.pop())