Title :
Random insertion into a priority queue structure
Author :
Porter, Thomas ; Simon, Istvan
Author_Institution :
Dept. of Computer Sci., Stanford Univ., Stanford, CA, USA
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 behaviour is discussed. Numerical data for the second model are also provided and analyzed.
Keywords :
algorithm theory; queueing theory; trees (mathematics); algorithms; heap; priority queue structure; probabilistic models; random insertion; Analytical models; Binary trees; Computational modeling; Data models; Educational institutions; Numerical models; Probability distribution; Analysis of algorithms; heap insertion; heap sort; priority queue;
Journal_Title :
Software Engineering, IEEE Transactions on
DOI :
10.1109/TSE.1975.6312854
