如何在python中构建maxHeap

Question

只要检查一下恢复方法。它显示索引超出范围错误。。我不知道为什么我一次又一次地犯这个错误

[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**

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:]

    

Answer 1

您必须检查i * 2 >= self.size。这就是导致错误的原因。因为当i * 2 == self.size时，self.heap[i*2+1]超出范围

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

另外，我看到您必须显式地打印b.heap[1:]。更好的解决方案是重写__str__()方法。 将此方法添加到BinaryHeap类：

def __str__(self):
    return str(self.heap[1:])

现在，您可以简单地执行以下操作：

print(b)

Answer 2

python中已经实现了一个max/min heap：

In [1]: import heapq
   ...:
   ...: h = []
   ...: heapq.heappush(h, 1)
   ...: heapq.heappush(h, 10)
   ...: heapq.heappush(h, 3)
   ...: heapq.heappush(h, 2)

In [2]: h
Out[2]: [1, 2, 3, 10]

In [3]: h[-2:]
Out[3]: [3, 10]

In [4]: h[::-1]
Out[4]: [10, 3, 2, 1]

如果你真的想实现你自己的版本，也许你可以看看this discussion。还有一个关于实现的问题。还有一个关于复杂性的问题