回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>只要检查一下恢复方法。它显示索引超出范围错误。。我不知道为什么我一次又一次地犯这个错误</p>
<pre><code>[42, 29, 18, 14, 7, 18, 12, 11, 5]
Traceback (most recent call last):
File "Untitled ", line 62, in <module>
b.dilMax()
File "Untitled ", line 48, in dilMax
self.perkDown(1)
File "Untitled ", line 37, in perkDown
max_child = self.getMaxChild(i)
File "Untitled ", line 31, in getMaxChild
if self.heap[i*2] > self.heap[i*2+1]:
IndexError: list index out of range**
</code></pre>
<pre><code>class BinaryHeap:
def __init__(self):
self . heap = [0]
self. size = 0
def swapUp(self, i):
while i // 2 > 0 :
if self.heap[i] > self.heap[i//2]:
self.heap[i], self.heap[i//2] = self.heap[i//2], self.heap[i]
i = i//2
def insert(self , value):
# add
self.heap.append(value)
self.size += 1
#maintain
self.swapUp(self.size)
def getMaxChild(self, i):
if i * 2 > self.size:
return i * 2
else:
if self.heap[i*2] > self.heap[i*2+1]:
return i * 2
return i * 2 + 1
def perkDown(self, i):
while i * 2 <= self.size:
max_child = self.getMaxChild(i)
if self.heap[i] < self.heap[max_child]:
self.heap[i], self.heap[max_child] = self.heap[max_child], self.heap[i]
i = max_child
def dilMax(self):
ret_val = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
# maintain the heap
self.perkDown(1)
b = BinaryHeap()
b.insert(42)
b.insert(29)
b.insert(18)
b.insert(14)
b.insert(7)
b.insert(18)
b.insert(12)
b.insert(11)
b.insert(5)
print(b.heap[1:])
b.dilMax()
print(b.heap[1:]
</code></pre>