3 Treaps: Using randomization to balance binary search trees

In chapter 2 we saw how it is possible to store elements and retrieve them based on their priorities by using heaps, and how we can improve over binary heaps by using a larger branching factor.

Priority queues are especially useful when we need to consume elements in a certain order from a dynamically changing list (such as the list of tasks to run on a CPU), so that at any time we can get the next element (according to a certain criterion), remove it from the list, and (usually) stop worrying about fixing anything for the other elements. The difference with a sorted list is that we only go through elements in a priority queue once, and the elements already removed from the list won’t matter for the ordering anymore.

3.1 Problem: Multi-indexing

3.1.1 The gist of the solution

3.2 Solution: Description and API

3.3 Treap

3.3.1 Rotations

3.3.2 A few design questions

3.3.3 Implementing search

3.3.4 Insert

3.3.5 Delete

3.3.6 Top, peek, and update

3.3.7 Min, max

3.3.8 Performance recap

3.4 Applications: Randomized treaps

3.4.1 Balanced trees

3.4.2 Introducing randomization

3.4.3 Applications of Randomized Treaps

3.5 Performance analysis and profiling

3.5.1 Theory: Expected height

3.5.2 Profiling height