Report Number: CS-TR-74-460
Institution: Stanford University, Department of Computer Science
Title: Random insertion into a priority queue structure.
Author: Porter, Thomas
Author: Simon, Istvan
Date: October 1974
Abstract: The average number of levels that a new element moves up when
inserted into a heap is investigated. Two probabilistic
models, under which such an average might be computed are
proposed. A "lemma of conservation of ignorance" is
formulated and used in the derivation of an exact formula for
the average in one of these models. It is shown that this
average is bounded by a constant and its asymptotic behavior
is discussed. Numerical data for the second model is also
provided and analyzed.