computer-science - 在 O(1) 时间内删除带有父指针的堆？

Question

所以问题是: 假设最小堆使用父指针，每个节点都包含一个指向其父节点的指针，而根节点有一个空指针。给定一个指向节点的指针，该节点不是树的根，包含堆中的最大键，删除的复杂度是多少？

答案是 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需要详细说明的问题。