book cover

Heaps
(A Sketch of Column 14 of Programming Pearls)

This column is about ``heaps'', a data structure that we'll use to solve two important problems.

Sorting. Heapsort never takes more than O(n log n) time to sort an n-element array, and uses just a few words of extra space.
Priority Queues. Heaps maintain a set of elements under the operations of inserting new elements and extracting the smallest element in the set; each operation requires O(log n) time.
For both problems, heaps are simple to code and computationally efficient.

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 Rest of the Column


14.1 The Data Structure
14.2 Two Critical Functions
14.3 Priority Queues
14.4 A Sorting Algorithm
14.5 Principles
14.6 Problems
14.7 Further Reading

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