Inserting a New Element into a Heap
In this paper a well known algorithm is studied which accomplishes the insertion of a new element into a heap. Under the assumption of uniformly distributed heaps and new elements, respectively, an explicit expression for the expected number of comparisons in terms of the binary representation of the number of elements in the heap is derived. From this, higher moments are calculated and asymptotically evaluated. Some numerical evidence is given that the mathematically derived results agree with results obtained in a simulation.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten