The first part of this book lays the foundations for the more advanced sections that we’ll discuss later. It focuses on discovering advanced data structures that provide an improvement over other more basic structures; for example, how we can improve binary heaps or make trees balanced, and how we can solve problems such as keeping track of things or groups of things?
Through these examples, we’ll show that there are many ways to perform operations on data, and as developers we need to get accustomed to the fact that the best way we can choose depends on the context and requirements. We thus need to look at requirements, examine the context, and learn to question our knowledge when we solve a problem, in order to spot the best solution for the specifics we are facing.
Chapter 2 introduces an advanced variant of binary heaps, the d-way heap. It also describes the structure we use, in each chapter in this part, to explain topics.
Chapter 3 further explores the advanced use of heaps with treap, a hybrid between a binary search tree and a heap that can also help in different contexts.