删除根节点并重新使用最大堆有麻烦

Question

我正在编写一个应从列表表示的maxheap中删除根节点的函数。删除根节点后，我无法重新排序以满足maxheap属性。这是我的代码：

def deleteMax(x):
    x.pop(0)
    curr = self.heap[0]
    rootindex = 0
    leftchild = rootindex*2+1
    rightchild = rootindex*2+2

    while current < x[leftchild] or current < x[rightchild] :
        if current < leftchild :
            x[rootindex ], x[leftchild] = x[leftchild], x[rootindex ]
            rootindex = leftchild
        else:
            x[rootindex ], x[rightchild] = x[rightchild], x[rootindex ]
            rootindex = rightchild

    return x

示例

x = []

Insert是我的插入函数，它以正确的顺序插入值。只是假设我正确插入

插入（10）

插入（5）

插入（14）

插入（9）

插入（2）

插入（11）

插入（6）

所以：x = [14、9、11、5、2、10、6]（正确）

但是当我调用deleteMax（）时，它可以很好地删除14，但是我留下了：

[[9，11，5，5，2，10，6]

当我希望它满足maxheap属性并使其为此时：

[[11，9，10，5，2，6]

Answer 1

用于除去最大堆根的算法是：

Move the last node in the heap to the root position.
Reduce the heap count by 1.
Set current to the root node.
while current is smaller than either of its children
    swap current with the largest child
    set current to index of the child you swapped it with

更新

您更新的代码几乎正确，但是不能保证您选择最大的子代。例如，如果您有这个：

        1
      5   7

您将1与5交换。您需要确保获得最大的孩子。因此：

current = 0
while (true)
    leftchild = current*2+1
    rightchild = current*2+2
    largest = current

    if (current >= size)
        break;
    if (x[current] < x[leftchild])
        largest = leftchild
    if (rightchild < size && x[largest] < x[rightchild])
        largest = rightchild
    if (largest == current)
        break
    swap(x[current], x[largest])
    current = largest

上面的代码确保您始终选择两个孩子中最大的一个，并且确保您不会无意中测试不存在的合适孩子。

Answer 2

您的算法不太正确。看一下此页面上的动画：https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

您现在正在做的是从最后一个元素开始，然后将其向上移动。相反，您需要获取最后一个元素，将其放在顶部（您刚刚弹出的元素以前所在的位置），然后将其向下移动。

如果只删除数组的第一个元素，则堆会中断，因为行都未对齐并且父/子链接已移动，因此您需要在该位置放一些东西。