Inserting a New Element into a Heap

Doberkat, Ernst-Erich GND

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.

Vorschau

Zitieren

Zitierform:

Doberkat, Ernst-Erich: Inserting a New Element into a Heap. Hagen 1981. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe