arrays - 当底层结构是数组时，为什么二进制堆中的删除是O（logN）操作
问题描述
我知道最小/最大堆中的删除总是发生在根部，当它发生时，被删除的节点被二进制堆中的最后一个节点替换，然后节点向下堆以找到它的正确位置，使其开启平均O(logN) 操作。
现在，二叉堆通常用数组表示。问题来了：如果数组中位置 [0] 的删除是 log(n)，因为所有右边的单元格都必须向左移动，才能填充空单元格。然后，**为什么最小/最大堆二叉树（在数组上表示）被认为是 O(logN) 操作 ** 而不是 O(n) 操作。
感谢您阐明混乱！
解决方案
...如果在位置 [0] 的数组中删除是 log(n)，因为所有右单元格必须向左移动，以填充空单元格。然后，**为什么最小/最大堆二叉树（在数组上表示）被认为是 O(logN) 操作 ** 而不是 O(n) 操作。
在您的第一段中，您正确地指出要删除根元素，必须将其替换为堆的最后一个元素，然后heapify从根向下应用操作。在这种情况下，并非所有正确的单元格都应该向左移动，因为您只更新根处的值（您也可以更新最后一个元素，或减少堆大小以忽略heapify操作中的元素），然后您 heapify从根。
heapify是 O(log(n))，无论堆是在数组上实现还是作为树实现。此外，它通常在数组上实现:)