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.