Deleting the root of a heap

Summary 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 a path 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 the expected number of comparisons and of interchanges are asymptotically equal to the respective numbers in the worst case.Some results were presented at the 19th Allerton Conference on Communications, Control, and Computing, University of Illinois, 1981, and the Second World Conference on Mathematics at the Service of Man, Las Palmas, Canary Islands, Spain, 1982Some of this work was done at the Fernuniversität, Hagen, West Germany