查找节点在数组中的位置（作为二进制堆）

Question

假设我想将一个节点插入到一个二叉堆中，如何在插入和堆化之后找到代表堆的数组中的节点索引？ 我需要在 O(log(log(n)).

中找到这个算法

谢谢大家

Answer 1

如果你看一下二叉堆中的插入，新节点放在末尾，然后向上移动他的分支找到它正确的位置。

因此，当您知道堆的大小时，您就知道新节点将插入到哪个分支中。分支大小为 log(n)。从这个位置，你也可以找到属于该分支的所有节点。

你所要做的就是沿着这个分支进行二分查找，你会在 log(log(n)) 中找到新节点的位置。