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

Question

是否有任何方法来估计能够 beat 的 d 堆中节点的插入深度(node_value / heap_max) * h，其中 h 是堆高度，并且 heap_max 被标准化为堆最小值？

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

Answer 1

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

Answer 2

根据Inserting a new element into a heap [Doberkat, 1981]，具有均匀密钥分布的二进制堆平均每次插入执行 1.6 次 UpHeap 操作。对于 d 堆，等效数量应该相当接近。