algorithm - 估计节点在 d-heap 中的插入深度

Question

是否有任何方法可以估计 d-heap 中节点的插入深度能够击败 (node_value/heap_max) * h，其中 h 是堆高度，heap_max 是归一化到堆最小值？

在这种特殊情况下，维护额外/历史数据以支持这种启发式算法是可行的，前提是其维护的时间复杂度为 O(1)。

Answer 1

不完全是 O(1)，但 O(loglogn)(对于所有实际目的 O(1))解决方案是存储某种级别统计信息。例如。您可以存储每个级别的最大值并进行二进制搜索。