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 ...