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

Question

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

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

谢谢大家

Answer 1

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