BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-74-460
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Random insertion into a priority queue structure.
        TYPE:: Technical Report
      AUTHOR:: Porter, Thomas
      AUTHOR:: Simon, Istvan
        DATE:: October 1974
       PAGES:: 28
    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.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-74-460