Estimating insertion depth of node in a d-heap
===

Is there any approach to estimating the insertion depth of a node in a d-heap that is able to beat `(node_value / heap_max) * h`, where h is the heap height, and heap_max is normalized to the heap minimum?

In this particular case, it is feasible to maintain extra/historical data to support this heuristic, given that the maintenance of which is O(1) in time. 