MaxHeap Python 实现

Question

我在 python 中找到了一个 implementation 的 MaxHeap。它按预期执行；但是，我对数组索引感到困惑——也就是说，因为最大元素存储在索引 0 处，我曾预计这会破坏 left/right 子索引（参考 __bubbleDown 方法。）

class MaxHeap:
    def __init__(self, items=[]):
        self.heap = []
        for i in items:
            self.heap.append(i)
            self.__floatUp(len(self.heap) - 1)

    def push(self, data):
        self.heap.append(data)
        self.__floatUp(len(self.heap) - 1)

    def peek(self):
        if self.heap[0]:
            return self.heap[0]
        else:
            return False
            
    def pop(self):
        if len(self.heap) > 0:
            self.__swap(0, len(self.heap) - 1)
            max = self.heap.pop()
            self.__bubbleDown(0)
        elif len(self.heap) == 0:
            max = self.heap.pop()
        else: 
            max = False
        return max

    def __swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def __floatUp(self, index):
        parent = index//2

        if self.heap[index] > self.heap[parent]:
            self.__swap(index, parent)
            self.__floatUp(parent)

    def __bubbleDown(self, index):
        left = index * 2
        right = index * 2 + 1
        largest = index
        if len(self.heap) > left and self.heap[largest] < self.heap[left]:
            largest = left
        if len(self.heap) > right and self.heap[largest] < self.heap[right]:
            largest = right
        if largest != index:
            self.__swap(index, largest)
            self.__bubbleDown(largest)
     

# tests
m = MaxHeap([95, 3, 21])
m.push(10)
print(str(m.heap[0:len(m.heap)]))
print(str(m.pop()))

如果第一个元素位于索引 0，则其左右子元素应计算为

左：0 * 2 => 0，

右：0 * 2 + 1 => 1

为什么这不是问题？

Answer 1

首先，您是对的，left 和 right 的计算不是应该的，但是...它仍然有效。

通过这种工作方式，我们得到了一个图，其中根的左边 child 实际上是一个 self-reference（一个循环）。因为当 parent 和 child 的值等于时，代码不会继续 __floatUp 或 __bubbleDown 递归调用，所以这个循环该图将永远不会被遍历。

所以我们这里有一个根节点最多只有一个realchild（它的右边child）。从那个 child 开始，事情 return 就正常了。除了这个奇怪的根之外，所有其他节点都以一个完全二叉树的子树为根。这个奇怪的根使“堆”的优化程度略有下降，因为树通常会比绝对必要的多一层。但它仍然会给出正确的结果。

其他备注

这段代码中还有一些奇怪的地方：

peek 堆为空时会报错。
peek 当根的值为假值时，如 0，将给出错误的结果。然后它将 return False。这两点应该通过应用与 pop 相同的 len 检查来解决。
在 pop 中，最终的 else 块永远不会执行，因为 len() 的值永远不会是 > 0 或 == 0 以外的任何值。这没有意义。
pop 会在堆为空时引发错误，因为那时会执行中间情况，代码会尝试从空列表中弹出

视频

您没有正确地将视频提供的内容表示为代码。

视频实际在 0:50 处解释了数组应从索引 1 开始，忽略索引 0。

在3:45以及更进一步，你可以看到演示者确实是这样编码的。您在此处提供的代码与他们的代码不同。看来你试图以某种方式对其进行调整，从而引入了比原始代码更多的问题。

MaxHeap Python 实现

MaxHeap Python implementation

python

arrays

heap

其他备注

视频