无法删除根节点并求助于最大堆

Question

我正在编写一个函数，该函数应该从列表表示的最大堆中删除根节点。删除根节点后，我无法重新排序以满足 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, 2, 10, 6]

当我想要它满足最大堆时属性并使其成为：

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

Answer 1

你的算法不太正确。看看这个页面上的动画：https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

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

如果我们只删除数组的第一个元素，那么堆就会中断，因为行都没有对齐并且 parent/child 链接发生了移动，因此您需要在那个位置放回一些东西。

Answer 2

去除max-heap根的算法是：

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

更新

您更新后的代码几乎是正确的，但不能保证您 select 最大 child。例如，如果你有这个：

        1
      5   7

您可以将 1 换成 5。您需要确保获得最大的 children。所以：

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

上面的代码确保您总是 select 两个 children 中最大的一个，并且还确保您不会无意中测试正确的 child在那里。

无法删除根节点并求助于最大堆

Having trouble deleting the root node and resorting in a max heap

python

heap

function

list

data-structures

例子

更新