估計d堆中節點的插入深度

Question

是否有任何方法來估計d堆中節點的插入深度，該堆能夠擊敗(node_value/heap_max) * h，其中h是堆高度，heap_max被歸一化爲堆最小？

在這種特殊情況下，維持額外/歷史數據來支持這種啓發式是可行的，因爲它的維護時間爲O（1）。

Answer 1

根據將一個新元素插入一個堆 [Doberkat，1981]具有統一密鑰分佈的二進制堆查看平均每個插入1.6個UpHeap操作。對於d堆，等效數字應該相當接近。

Answer 2

不完全是O（1），但O（loglogn）（對於所有實際用途O（1））解決方案將存儲某種等級統計。例如。您可以存儲每個級別的最大值並執行二進制搜索。