Heaps on Heaps
Gastón H. Gonnet, J. Ian Munro · SIAM Journal on Computing · 1986
As part of a study of the general issue of complexity of comparison based problems, as well as interest in the specific problem, we consider the task of performing the basic priority queue operations on a heap. We show that in the worst case: $\lg \lg n \pm O(1)$ comparisons are necessary and sufficient to insert an element into a heap. (This improves the previous upper and lower bounds of $\lg n$ and $O(1)$.) $\lg n + \log ^ * n \pm O(1)$ comparisons are necessary and sufficient to replace the maximum in a heap. (This improves the previous upper and lower bounds of $2\lg n$ and $\lg n$.) $1.625n + O(\lg n\log ^ * n)$ comparisons are sufficient to create a heap. $1.37 \ldots n$ comparisons are necessary not only in the worst case but also on the average. Here lg indicates the logarithm base 2 and $\log ^ * $ denotes the iterated logarithm or number of times the logarithm base 2 may be taken before the quantity is at most 0.