3 Treaps: Using Randomization to Balance Binary Search Trees

In chapter 2 we have seen 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 (like the list of tasks to run on a CPU), so that at any time we get the next element (according to a certain criterion), remove it from the list and (usually) not worry anymore 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, Peak, 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

3.5.3   Profiling Running Time

3.5.4   Profiling Memory Usage

3.5.5   Conclusions

3.6      Summary