algorithm - 插入后查找二进制堆节点的位置

Question

假设我想将一个节点插入到二进制堆中，如何在插入和堆化后找到堆中节点的索引？二叉堆表示为一个数组。我需要在 O(log(log(n)) 中找到这个算法。

我知道如何在 log n 复杂度中找到它，但在 log log n 中找不到它。

谢谢你们。

Answer 1

我们来看看节点通常是如何插入的。它被附加到数组的末尾，然后与它的父级交换，直到它到达根或变得大于或等于它的父级（我假设我们有一个最小堆）。这就是为什么我们只需要在从它到根的路径中找到这个元素的位置。但是这条路径是排序的（由于堆的属性）。这就是为什么我们可以使用二进制搜索来找到它在这条路径中的位置。路径的长度是O(log n)，所以二分查找在O(log(log n)).