Я писал приоритетную очередь как часть подготовки к интервью и получил ошибку, которую не могу отследить.Мой код PQ:
class PQ:
def __init__(self, capacity):
self.a = [None] * capacity
self.size = 0
def sift_down(self, i):
while 2*i+1 < self.size:
l, r = 2*i+1, 2*i+2
j = l
if r < self.size and self.a[r] > self.a[l]: j = r
if self.a[i] >= self.a[j]: break
self.a[i], self.a[j] = self.a[j], self.a[i]
i = j
def sift_up(self, i):
assert self.a[i] is not None
assert self.a[(i-1) // 2] is not None
while self.a[i] > self.a[(i-1) // 2]:
self.a[i], self.a[(i-1) // 2] = self.a[(i-1) // 2], self.a[i]
i = (i - 1) // 2
def extract_max(self):
m = self.a[0]
self.size -= 1
self.a[0] = self.a[self.size]
self.sift_down(0)
return m
def insert(self, x):
self.a[self.size] = x
if self.size > 0: self.sift_up(self.size)
self.size += 1
И затем я проверяю его:
pq = PQ(6)
pq.insert(200)
pq.insert(10)
print(pq.extract_max())
pq.insert(5)
pq.insert(500)
print(pq.extract_max())
Все работает до 'pq.insert (500)':
File "pq.py", line 35, in insert
if self.size > 0: self.sift_up(self.size)
File "pq.py", line 21, in sift_up
while self.a[i] > self.a[(i-1) // 2]:
TypeError: '>' not supported between instances of 'int' and 'NoneType'
Iу меня отлажены значения в позициях i и (i - 1) // 2 всеми известными мне методами, утверждающие ничего не выбрасывают, я полностью потерян!