Chapter 16. Advanced Data Structures
CHAPTER GOALS
To learn about the set and map data types
To understand the implementation of hash tables
To be able to program hash functions
To learn about binary trees
To become familiar with the heap data structure
To learn how to implement the priority queue data type
To understand how to use heaps for sorting
In this chapter we study data structures that are more complex than arrays or lists. These data structures take control of organizing their elements, rather than keeping them in a fixed position. In return, they can offer better performance for adding, removing, and finding elements.
You will learn about the abstract set and map data types and the implementations that the standard library offers for these abstract types. You will see how two completely different implementations—hash tables and trees—can be used to implement these abstract types efficiently.
Sets
In the preceding chapter you encountered two important data structures: arrays and lists. Both have one characteristic in common: These data structures keep the elements in the same order in which you inserted them. However, in many applications, you don't really care about the order of the elements in a collection. For example, a server may keep a collection of objects representing available printers (see Figure 1). The order of the objects doesn't really matter.
In mathematics, such an unordered collection is called a set. You have probably learned some set theory in a course in mathematics, ...
Get Big Java, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
