Cam*_*all 3 algorithm time-complexity binary-heap data-structures
从堆中删除叶节点的时间复杂度是多少？
我想如果你不知道节点在哪里,它就会记录,因为你必须找到它.
但是,如果你已经知道节点在哪里,它应该是O(1)对吗？既然你可以删除它而你不必重新堆积所有东西？
请记住,二进制堆必须是完整的二叉树,所以如果你删除除最后一个叶子之外的叶子,你需要移动一些东西来代替它.一种方法是将它与最后一个叶子交换,删除最后一个叶子,然后执行一个冒泡步骤以确保堆属性仍然成立.除了实际定位要删除的叶节点的时间之外,这需要时间O(log n).
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
2253 次 |
| 最近记录： |