Lecture 20
Heapsort has a worst case complexity of
O(N log N). It can be viewed as an efficient implementation of Selection
sort.
On the way to writing our the
heapsort algorithm we saw detailed pseudo-code for restoring the heap property
up the tree (as in insert operations) and restoring the heap property down the
tree (as in deletes). I then wrote out the heapsort algorithm make use of
restoreDown.
On Friday we will
consider the task of building a heap.
Posted: Wed - March 2, 2005 at 08:52 PM