从堆中删除叶节点的时间复杂度是多少？
我想如果你不知道节点在哪里，它会是 log n，因为你必须找到它。
但是如果您已经知道节点在哪里，它应该是 O(1) 对吗？既然您可以将其删除，而不必重新堆放所有内容？
最佳答案
请记住，二叉堆必须是完整的二叉树，因此如果您删除了最后一片叶子以外的一片叶子，您将需要移动一些东西来取代它的位置。一种方法是将它与最后一个叶子交换，删除最后一个叶子，然后执行冒泡步骤以确保堆属性仍然有效。除去实际定位要移除的叶节点的时间，这需要时间 O(log n)。
希望这对您有所帮助!
关于algorithm - 从二叉堆中删除叶子的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20015295/