edith@ai.toronto.edu (Edith Fraser) (02/27/90)
Department of Computer Science, University of Toronto (SF = Sandford Fleming Building, 10 King's College Road) ------------------------------------------------------------- COMBINATORICS & THEORY SF1105, at 3:00 p.m., 5 March 1990 Ryan Hayward University of Bonn "Average Case Analysis of Heap Construction" In 1964 Williams introduced the now famous algorithm "Heapsort". Soon after, Floyd pointed out that the construction phase of Williams' algorithm could be performed more efficiently... IN THE WORST CASE. Today, virtually any textbook version of heapsort uses the Floyd heap construction subroutine. But is this preference for Floyd's heap construction over Williams' justified ... IN THE AVERAGE CASE? Until only recently the answer to this question was not known. In the first part of the talk I will give a mini-survey of algorithms for heap construction, and briefly discuss the average case analysis of these algorithms. In the latter part of the talk I will discuss in some detail my recent research (in collaboration with Colin McDiarmid) on the average case analysis of Williams' heap construction... and the answer to the above question will be revealed.