3

从堆中删除叶节点的时间复杂度是多少？

我想如果你不知道节点在哪里，它会是 log n 因为你必须找到它。

但是，如果您已经知道节点在哪里，它应该是 O(1) 对吗？既然您可以删除它而不必重新堆放所有东西？

4

1 回答 1

7

请记住，二叉堆必须是完整的二叉树，因此如果您删除最后一个叶子以外的叶子，则需要移动一些东西来代替它。一种方法是将它与最后一个叶子交换，删除最后一个叶子，然后执行冒泡步骤以确保堆属性仍然成立。除了实际定位要移除的叶节点的时间之外，这需要时间 O(log n)。

希望这可以帮助！

于 2013-11-16T06:35:15.877 回答