Skip to Main Content
Programming Pearls, 2nd Edition
book

Programming Pearls, 2nd Edition

by Jon Bentley
September 1999
Intermediate to advanced content levelIntermediate to advanced
256 pages
7h 38m
English
Addison-Wesley Professional
Content preview from Programming Pearls, 2nd Edition

Column 14: Heaps

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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

The Practice of Programming

The Practice of Programming

Brian W. Kernighan, Rob Pike
The Programmer's Brain

The Programmer's Brain

Felienne Hermans
Programming Interviews Exposed, 4th Edition

Programming Interviews Exposed, 4th Edition

John Mongan, Noah Suojanen Kindler, Eric Giguere
Programming Rust, 2nd Edition

Programming Rust, 2nd Edition

Jim Blandy, Jason Orendorff, Leonora F. S. Tindall

Publisher Resources

ISBN: 9780134498058Purchase book