algorithm – 从二进制堆中删除叶子的时间复杂度
发布时间：2020-12-15 04:15:23 所属栏目：Java 来源：网络整理
导读：从堆中删除叶节点的时间复杂度是多少？ 我想如果你不知道节点在哪里,它就会记录,因为你必须找到它. 但是,如果你已经知道节点在哪里,它应该是O(1)对吗？既然你可以删除它而你不必重新堆积所有东西？ 解决方法 请记住,二进制堆必须是完整的二叉树,所以如果你删
|
从堆中删除叶节点的时间复杂度是多少？
我想如果你不知道节点在哪里,它就会记录,因为你必须找到它. 但是,如果你已经知道节点在哪里,它应该是O(1)对吗？既然你可以删除它而你不必重新堆积所有东西？ 解决方法
请记住,二进制堆必须是完整的二叉树,所以如果你删除除最后一个叶子之外的叶子,你需要移动一些东西来代替它.一种方法是将它与最后一个叶子交换,删除最后一个叶子,然后执行一个冒泡步骤以确保堆属性仍然成立.除了实际定位要删除的叶节点的时间之外,这需要时间O(log n).
希望这可以帮助！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |