从堆中删除叶节点的时间复杂度是多少?
我想如果你不知道节点在哪里,它将是log n,因为你必须找到它。
但是如果你已经知道节点在哪里,它应该是O(1)对吗既然你可以把它移走,你就不用把所有东西都重新堆起来了?

最佳答案

记住,二叉堆必须是完整的二叉树,所以如果你去掉了最后一片叶子以外的一片叶子,你就需要移动一些东西来代替它一种方法是将其与最后一个叶交换,删除最后一个叶,然后执行冒泡步骤以确保heap属性仍然有效。除了实际定位要删除的叶节点的时间外,这还需要时间o(log n)。
希望这有帮助!

10-06 05:06
查看更多