Inserting a new element into a heap
This paper analyzes a well known algorithm which inserts a new element into a heap in such a way that the heap condition is not violated. The analysis is done with respect to the average number of comparisons which are needed to find the correct position for the new element. In contrast to Porter and Simon, who have analyzed this algorithm, too (IEEE Trans. Softw. Eng., vol. SE-1, 1975, 292-298) the present paper gives an explicit formula for the quantities in question (in terms of the binary representation of the number of elements involved). This is done under the assumption that all possible heaps are equally probable and the element to be inserted is equidistributed, too. Since the components of the heap are assumed tobe real numbers, the assumption on the distribution must be formulated in terms of Probability Theory, rather than in a combinatorial manner, and consequently methods of Analysis are used rather heavily. Moreover it is shown that the usual finite discrete model for analyzing the average performance of sorting algorithms can be embedded into the model via a functor which preserves probabilities, and expectations.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten