Deleting the Root of a Heap

Doberkat, Ernst-Erich GND

Using a continuous model, the average behavior of the familiar algorithm for root deletion is considered, when every heap has the same probability to occur. The analysis centers around the notion of a viable path in the tree representation, i .e. such paths the label which replaces the label of the root may be allowed to travel when the heap is reconstructed. In case the size of the heap is a power of 2 it is shown that both fhe expected number of comparisons and of interchanges are asymptotically equal to the respective numbers in the worst case.

Vorschau

Zitieren

Zitierform:

Doberkat, Ernst-Erich: Deleting the Root of 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