This column is about ``heaps'', a data structure that we'll use to solve two important problems.
This column has a bottom-up organization: we start at the details and work up to the big picture. The next two sections describe the heap data structure and two functions to operate on it. The two subsequent sections use those tools to solve the problems mentioned above.
The teaching material contains overhead transparencies based on this column; the slides are available in both Postscript and Acrobat.
The code for Column 14 contains the code for priority queues, and the code for Column 11 contains the code for Heapsort.
The animations of sorting algorithms show Heapsort at work. (But heed the warning on that page that the sleazy implementation leaves the first element of the array dangling in mid-air.)
Copyright © 1999 Lucent Technologies. All rights reserved. We 6 Oct 1999