Algorithmic Thinking, 2nd Edition

8HEAPS AND SEGMENT TREES

Data structures organize our data to make it possible to accelerate certain operations. For example, in Chapter 1, we learned about hash tables, which speed up the search for a specified element in a collection.

In this chapter, we’ll learn two new data structures: heaps and segment trees. A heap is what you want whenever you need the maximum (or minimum) element; a segment tree is what you want when you need to perform queries on pieces of an array. In our first problem, we’ll see how heaps turn slow maximum computations into fast heap operations; in our second and third problems, we’ll see how segment trees do similarly ...