computer-science - 在 O(1) 时间内使用父指针在堆中删除？

Question

那么问题来了:
假设 min heap 使用父指针，这样每个节点都包含一个指向其父节点的指针，而根节点具有一个空指针。给定一个指向节点的指针，它不是树的根，包含堆中的最大键，删除的复杂度是多少？

答案是 O(1) 但这对我来说没有意义。因为堆总是平衡的，所以你不能用相邻的节点替换删除的节点，你必须缩放树的长度 O(log N) 才能找到树中最后输入的节点，对吗？为什么这个问题的答案不是 O(log N)？

例如:

一个堆以 1、100、2、3、4、5 的顺序插入，1 作为根节点，100 和 2 和子节点，3 和 4 作为 100 的子节点，5 作为 2 的子节点。

删除 100 需要用 5 替换它，这需要 O(log N) 时间来访问，对吗？

Answer 1

您正在寻找的概念是“摊销常数时间” - 即平均值为 O(1) - 即使有时单个操作需要更长的时间，例如上面的示例。看看this扩展描述的问题。