Random insertion into a priority queue structure

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... View More