algorithm - d ヒープ内のノードの挿入深度の見積もり

Question

(node_value / heap_max) * hh はヒープの高さであり、heap_max はヒープの最小値に正規化されている場合、d ヒープ内のノードの挿入深度を推定する方法はありますか?

この特定のケースでは、このヒューリスティックをサポートするために余分な/履歴データを維持することが可能です。

Answer 1

Not exactly O(1), but a O(loglogn) (for all practical purposes O(1) ) solution would be to store some kind of level stat. Eg. You can store max of each level and do a binary search.

Answer 2

Inserting a new element into a heap [Doberkat、1981]によると、一様なキー配布によるバイナリ ヒープでは、挿入ごとに平均 1.6 の UpHeap 操作が見られます。d ヒープの場合、相当する数はかなり近いはずです。