如何跟踪插入到堆中的位置:我认为使用检查每个子树高度的函数会将算法从 O(log N) 降级为 O(N)。
那么你是在每个节点中保留一个变量还是在具有最后一个插入点的堆中保留一个变量(如何定义?)。
最佳答案
堆是“几乎满”的二叉树。因此,您只有一个选择来插入新元素,不需要高度检查 - 但需要一个指向下一个元素应插入的位置的指针。 这当然足以确保 O(logn) 的高度
关于java - 计算堆中的空闲空间?跟踪最后一次插入?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5288969/